二分查找法

定义

二分查找法也叫折半查找法，就例如我心中想一个范围在0～100的数字，让人猜这个数字是多少，那么第一次对方猜是50，如果我说大了那么范围就缩小到51～100，仅为原来的一半，每次猜数范围都会缩小到原来的一半，那么这样猜测的次数就仅为log2N。

注意⚠️：二分查找法必须在线性表且有序的情况下使用，无序/链表情况下并不适用。

图解

以数组  1 2 3 5 7 9 11 15 为例

（1）查找2---->查找成功情况

⚠️：此处mid的计算是向下取整。

因为mid>2,因此high=mid-1

此时mid==2，查找成功。

（1）查找4--->查找不成功情况

前面步骤一致：

因为mid<4因此low=mid+1，此时三者重合

mid=3<4,因此low=mid+1往右走，此时不满足low<=high，于是查找不成功，退出返回-1。

代码

这是闭区间[low,high]的代码，左闭右开参考算法竞赛入门书本上的代码。仅有细微差别。

int bsearch(int* arr, int arrSize, int value){
    int mid;
    int low = 0;
    int high = arrSize - 1;

    while(low <= high){
        mid = low + (high - low)/2;
        if(mid == value) return mid;
        else if(mid > value) high = mid -1;
        else low = mid + 1;
    }
    return -1; //查找失败

}

例题：剑指 Offer 53 - II. 0～n-1中缺失的数字

这题题目描述说是有序的数，因此有两种思路第一种就是常规的遍历数组与其下标一一对比，也是我一开始想到的方法，这种方法在单次查询中适用多次就效率很低。代码如下：

注意⚠️：要考虑数组为 0～n-2的情况 此时返回的是numSize也就是最后一位数，我一开始的解法没有考虑到但是也碰巧通过。

int missingNumber(int* nums, int numsSize){
    int t=0;
    printf("%d",numsSize);
    while(t < numsSize){
        printf("%d %d\n",t,nums[t]);
        if(nums[t]!=t) break;
        t++;
    }
    // printf("%d",);
    return t;
}

第二种思路：

使用二分查找法做细微变化，每次查找到的数字若与其下标也就是mid相等的话说明其左侧所有数字必然没有缺失，那么我们就往右边走在本文把右边不等的部分数组称为右不等子数组，low=mid+1；若是查找到的数字与mid不相等则向左走（左等子数组）此时high=mid-1；这样循环往复，每次low都指向右不等子数组的第一位，high指向左等子数组的最后一位。因此最后返回low即可。

int missingNumber(int* nums, int numsSize){
    int mid;
    int low=0;
    int high=numsSize-1;
    while(low<=high){
        mid = low + (high-low)/2;
        if(nums[mid]==mid) low = mid + 1;
        else high = mid - 1;
    }
    return low;
}

扩展：二分查找上下界

（1）下界     

在查找的时候存在这样的情形，我们查找value在数组中有多个重复，此时我们要查找第一个可以插入value的位置（也可以理解为第一次出现value的位置），也就是下界。这种情况应该如何解决？

思路：此时必须采用左闭右开区间的方法，具体原因在与我们代码中high与low值的变化不对称，若是依然采用上述的区间操作会陷入死循环，这么说有些难以理解，建议读者可以自行单步运行协助理解； 每当数组中的值>=value时 我们就往左移动，注意此处是high=mid，否则当arr[mid]<value时，low=mid+1，最后这个low指向的就是第一个v出现的位置。

int lower_bound(int * arr, int v){
    int low = 0;
    int high = length;
    int mid;
    while (low < high)
    {   
        mid = low + (high - low)/2;
        if(arr[mid] >= v ) high = mid; //只要大于这个值那么就往左走
        else low = mid + 1;//小于这个值就往右走，因为此处mid已经小于v了，所以low等于mid+1
        
    }
    return low;//返回的是第一个等于v的位置
}

int main(){
    int arr[length]={0,1,2,2,2,5,6,7,8,9};
    int res;
    int v= 2;
    res = lower_bound(arr,v);
    printf("\nres = %d\n",res);
    return 1;
}

（2）上界

注意⚠️：此处查找的是在数组中有序插入v值的位置（也就是最后一次出现value的位置的后一个位置）

#define length 10
#include <stdio.h>
int higher_bound(int * arr, int v){
    int low = 0;
    int high = length;
    int mid;
    while (low < high)
    {   
        mid = low + (high - low)/2;
        if(arr[mid] <= v ) low = mid + 1; //只要小于等于这个值那么就往右走
        else high = mid ;//大于这个值就往左走，因为此处mid已经小于v了，所以low等于mid+1
        
    }
    return high;//返回的是最后一个v的后一个位置
}

int main(){
    int arr[length]={0,1,2,2,2,5,6,7,8,9};
    int res;
    int v= 2;
    res = higher_bound(arr,v);
    printf("\nres = %d\n",res);
    return 1;
}

*********数组中只有一个小于等于v的数时，high会越界 注意！！