二分查找——没有想象中的容易（详解各种变式，超深度理解，c++）

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) {
        //int mid = (right + left) / 2;  //不建议使用
           int mid = left + (right-left)/2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}

这就是最基本的二分查找，若查找成功，则立即返回target下标mid，否则返回-1

老生常谈的细节：

（1）mid = left + (right-left)/2 , 之所以这样写，避免了right与left相加除以2，分子相加时可能超过INT_MAX范围的问题

（2）right = 数组长度-1 时，while中一定对应的是left<=right , 因为每次搜索都是在[left, right]闭区间上，只有left！=right 才会停止查找

（3）建议先判断一下数组是否为空（empty）

（4）不存在target时，一定返回-1

（5）理解一下mid = left + (right-left)/2 总是返回中间数偏向于left的一侧（自己理解一下，有用）

然后，就是变式

如果我一定要写成：right = 数组长度呢？我怎么修改代码呢？（这就是为什么网上会有两种模板）

模板如下，改动地方有三个：

1. right = 数组长度（不要减一）

2.while判断条件是 left<right（而不是left<=right）

3. right = m（不是right = mid +1）

 1 int main()
 2 {
 3     vector<int> v={1,2,3,4,5,6,7};
 4     int key = 9,index=-1;
 5     int l=0,r=v.size();
 6     while(l<r)
 7     {
 8         int m =l+(r-l)/2;
 9         if(v[m]==key)
10         {
11             index = m;
12             break;
13         }
14         else if(v[m]<key)
15             l = m+1;
16         else
17             r = m;
18     }
19     cout<<"index:"<<index<<endl;
20     return 0;
21 }

第二份代码和第一份效果一模一样，如何理解呢？

第二份中，r设定为数组长度，所以搜索空间是[left, right) , 当left==right时，就已经可以退出了，所以while中写left<right。如果mid值与key值不相等，那么由于mid值已经搜索过了，

所以下次检索时，是从[left,mid) 或 [mid+1,right) 开始，所以写成了right = mid（而不是right = mid +1）

继续变式：

（1）想要返回第一个等于key的下标，如{1,2,3,3,3,4}中，key=3，则返回下标

find_first_equal

 1 int find_first_equal(vector<int> v, int key)
 2 {
 3     int l=0, r =v.size()-1;
 4     int index;
 5     while(l<=r)
 6     {
 7         int m = l+(r-l)/2;
 8         if(v[m]>=key)
 9             r = m-1;
10         else
11             l = m+1;
12     }
13     if(l>=0&&l<=v.size()-1&&v[l]==key)
14         index = l;
15     else
16         index = -1;
17     cout<<"find_first_equal,index:"<<index<<endl;
18     return index;
19 }

技术关键点在于：

第一，退出的时候，我们要的是left还是right，想一想。

第二，如果key值不存在，那么left可能不合法，所以要判断left在正常范围内，并且要和key对上。

（2）想要返回最后一个等于key的下标，如{1,2,3,3,3,4}中，key=3，则返回下标4

find_final_equal

 1 int find_final_equal(vector<int> v, int key)
 2 {
 3     int l=0, r =v.size()-1;
 4     int index;
 5     while(l<=r)
 6     {
 7         int m = l+(r-l)/2;
 8         if(v[m]<=key)
 9             l = m+1;
10         else
11             r = m-1;
12     }
13     if(r>=0&&r<=v.size()-1&&v[r]==key)
14         index = r;
15     else
16         index = -1;
17     cout<<"find_final_equal,index:"<<index<<endl;
18     return index;
19 }

（3）想要返回第一个大于key的下标，如{1,2,3,4,5}中，key=3，则返回下标3

find_first_bigger

 1 int find_first_bigger(vector<int> v, int key)
 2 {
 3     int l=0, r =v.size()-1;
 4     int index;
 5     while(l<=r)
 6     {
 7         int m = l+(r-l)/2;
 8         if(v[m]<=key)
 9             l = m+1;
10         else
11             r = m-1;
12 
13     }
14     if(l<=v.size()-1)
15          index = l;
16     else
17         index = -1;
18     cout<<"find_first_bigger,index:"<<index<<endl;
19     return index;
20 }

参考文档：

1.https://blog.csdn.net/asmartkiller/article/details/96179338

2.https://www.cnblogs.com/luoxn28/p/5767571.html

原文链接: https://www.cnblogs.com/qiezi-online/p/12932252.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/349939

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

二分查找——没有想象中的容易（详解各种变式，超深度理解，c++）

相关推荐