查找 --- 二分查找法

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

转换为完全二叉树