1. 思想
二分查找（Binary Search）,它的前提是線性表中的記錄必須是關(guān)鍵碼有序（通常從小到大有序）宪躯，線性表必須采用
順序存儲。
基本思想：在有序表中，取中間記錄作為比較對象削祈，若給定值與中間記錄的關(guān)鍵字相等，則查找成功肮砾；若給定值小于中間記錄的關(guān)鍵字诀黍，則在中間記錄的左半?yún)^(qū)域繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵字仗处，則在中間記錄的右半?yún)^(qū)域繼續(xù)查找眯勾。不斷重復(fù)以上過程枣宫，直到查找成功，或所有查找區(qū)域無記錄吃环，查找失敗為止也颤。
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. 推導(dǎo)
1.最好的情況 當(dāng)然是1次了
2.最壞的情況 相當(dāng)于求完全二叉樹的深度 |log2^N| + 1
轉(zhuǎn)換為完全二叉樹
