1. 思想
二分查找（Binary Search）,它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用
顺序存储。
基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区域继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区域继续查找。不断重复以上过程，直到查找成功，或所有查找区域无记录，查找失败为止。
2. 代码
int Binary_search(int *a, int n, int key) {
int low, height, mid;
low = 0;
height = n;
int k_whiler = 0;
while (low <= height) {
k_whiler++;
printf("第 %d 次查找 \n",k_whiler);
mid = (low + height)/2;
if(key < a[mid]) {
height = mid - 1;
}else if (key > a[mid]) {
low = mid + 1;
} else {
return mid;
}
}
return 0;
}
#pragma mark - 使用
int a[] = {0,1,16,24,35,47,59,62,73,88,99};
int length = sizeof(a)/sizeof(int);
int search = Binary_search(a, length-1, 88);
3. 推导
1.最好的情况 当然是1次了
2.最坏的情况 相当于求完全二叉树的深度 |log2^N| + 1
转换为完全二叉树
