二分查找的正确写法

分手后的思念是犯贱 2021-10-29 07:16 302阅读 0赞

参考文献

[https://www.cnblogs.com/webary/p/4753231.html][https_www.cnblogs.com_webary_p_4753231.html]

[https://blog.csdn.net/malimingwq/article/details/97418866][https_blog.csdn.net_malimingwq_article_details_97418866]

## 为什么使用low + (high - low) / 2而不使用(high + low) / 2呢？ ##

防止溢出！

> high = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824  
> low = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824

然后我们将这两个数值相加，看结果是什么。

> high + low = 1000 0000 0000 0000 0000 0000 0000 0000  
> = 2147483648 as unsigned 32-bit integer  
> = -2147483648 as signed 32-bit integer  
> (high + low) / 2 = 1100 0000 0000 0000 0000 0000 0000 0000 = -1073741824  
> (high + low) >>> 1 = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824  
> low + (high - low) / 2 = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824  
>

作为**带符号的32位整数**，它是溢出的并且翻转为负。因此`(high + low) / 2`是错误的，因为`high + low`的运算结果可能超出当前类型所表示的范围的。

如果作为**无符号32位整数**运算，总和是正确的。所需要的就是将它除以2。

在Java运算中不支持**无符号整数**，所以我们一般选择low + (high - low) / 2来防止溢出，但有一种是这样写的low + (high - low) >>> 1，在Java中**>>>**和**>>**的区别，则在于**无符号**和**有符号**。如果使用>>，会将符号位也参与运算。

> (high + low) >> 1 = 1100 0000 0000 0000 0000 0000 0000 0000 = -1073741824

一般来说>>和>>>比除法的/的运行效率高，但是经过编译器的优化，他们效率并不相差多少，工作中尽量风格和同事统一，不要擅自使用**位运算**，这样有可能会造成阅读困难，而且效率也不能提高多少。

## 为什么使用low + ((high - low) >> 1)而不使用low + (high - low) >> 1呢？ ##

C和java语言的 移位>>的优先级 低于  
加减+的优先级  
所以 mid = low + (high-low)>>1; 是错的  
所以在c语言中，正确的写法为  
mid = low + ((high-low)>>1);

大体思路我们应该都很清楚：有三个游标，一个low在头，一个high在尾，还有一个mid指向中间，如果要检索的数据value比中间的元素arr\[mid\]小，那么应该在\[low,mid)区间继续查找，即将high指向mid前面那个元素（也许你可能认为是指向mid元素的位置）；如果要检索的数据value比中间的元素arr\[mid\]大，那么应该在(mid,high\]区间继续查找，即将low指向mid后面那个元素（也许你可能认为是指向mid元素的位置）。一直执行这个步骤来缩小搜索区间直到找到arr\[k\]==value返回k 或 low>high时返回-1表示没找到。

typedef int DataType;
    int binarySearch(const DataType arr[],const DataType value,size_t len)
    {
        int low = 0, high = len-1, mid;
        while(low <= high) {
            mid = low + ((high-low)>>1); //思考为什么不写作(high+low)/2;
            if(value-arr[mid]<1e-6 && arr[mid]-value<1e-6)//思考为何不写作arr[mid]==value
                return mid;
            if(value<arr[mid])
                high = mid-1;    //如果写作high = mid;可以吗
            else
                low = mid+1;    //如果写作low = mid;可以吗
        }
        return -1;
    }

在看完了上面的代码后，你有木有想到代码中注释部分的问题？当你第一遍写代码的时候真的考虑到了吗，如果没考虑这些会有什么过果呢？下面让我们来一一道来：

（1）第六行如果写作mid = (high+low)/2;，有木有发现high+low有点蹊跷？如果你看出来了，恭喜你说明你对数据类型对应的取值范围很了解！当DataType定义为int型时，**两个int相加，不要以为不会越界**哈~另外改成移位操作同样完成了除以2一样的效果，但是效率却提高了。如果用移位的话一定要记得**移位运算优先级很低**，所以记得加括号！！记得加括号！括号！（重要的事说三遍，哈哈）

（2）第七行说好的判等呢，为嘛写成了区间的形式？这个嘛，就要考虑代码可重用性，因为细心的你可能会发现，传入的第一个参数是数组类型，什么类型的数组？这里暂时定义为int,那如果是**float**呢？**double**呢？判等还用==？所以这里考虑的是普遍情况，通过将两个数的差值在很小范围内来表示他们相等，int时照样适用。(两个浮点数相减的结果 小于一个极小的数，则可以认为两个浮点数相等)

（3）第10行第12行，才开始写的时候可能会纠结是不是要减1或者加1，当然还有第五行是写low <= high还是low < high？举几个让另一种情况出现问题的例子然后你就会明白其中的奥秘了。

好了，基本上要注意主要的问题就这些了，下面给出一个用模板函数写好的完整代码吧！

#include<vector>
    #include<iostream>
    using namespace std;
    
    //二分查找模板
    template<typename T1,typename T2>
    int binarySearch(const T1 &arr,const T2 &value,size_t len)
    {
        int low = 0, high = len-1, mid;
        while(low <= high) {  /* 注意这里是小于等于 */
            mid = low + ((high-low)>>1); //思考为什么不写作(high+low)/2;
            if(value-arr[mid]<1e-6 && arr[mid]-value<1e-6)//思考为何不写作arr[mid]==value
                return mid;
            if(value<arr[mid])
                high = mid-1;    //如果写作high = mid;可以吗
            else
                low = mid+1;    //如果写作low = mid;可以吗
        }
        return -1;
    }
    
    int main()
    {
        double arr[10];
        int i;
        for(i=0; i<10; i++)
            arr[i] = i;
        for(i=-1; i<11; i++)
            cout<<"the index of '"<<i<<"': "<<binarySearch(arr,i,10)<<endl;
    
        cout<<endl;
        vector<int> arr_i(arr,arr+10);
        for(i=-1; i<11; i++)
            cout<<"the index of '"<<i<<"': "<<binarySearch(arr_i,i,arr_i.size())<<endl;
        return 0;
    }

##  ##

##    为什么是low = mid+1; high = mid-1;  而不是low = mid; high = mid;？ ##

防止出现死循环，如果high=mid/low=mid，有特殊的情况，high会永远等于low，就成了死循环了。

例如，我们对数组a={2,2}进行二分查找，假设我们查找3：

> 2 2
> 
> low high
> 
> mid

如果是 low=mid 的更新方式，那么上面的例子会出现死循环。

mid=low+(high-low)/2=0;  
a\[mid\]=a\[0\]=a\[mid\]=2

所以，a\[mid\]<3  
因此，low=mid=0。注意此时low和mid还是都指向0，说明此时出现**死循环**了！！！

综上所述，low=mid; 会导致死循环。

**2.二分查找返回key(可能有重复)第一次出现的下标x，如果不存在返回-1**

二分查找（Binary Search）常见问题解决方法总结

[https://blog.csdn.net/han\_\_\_\_shuai/article/details/75249037][https_blog.csdn.net_han_shuai_article_details_75249037]

[https://blog.csdn.net/renwotao2009/article/details/51860436][https_blog.csdn.net_renwotao2009_article_details_51860436]

[https://www.cnblogs.com/wuyuegb2312/archive/2013/05/26/3090369.html\#][https_www.cnblogs.com_wuyuegb2312_archive_2013_05_26_3090369.html]

[https://www.cnblogs.com/moonbay/p/4886799.html][https_www.cnblogs.com_moonbay_p_4886799.html]

终止：  
此时left>=right。在每次循环结束时，left总是x的第一个可能下标，array\[right\]总是第一个等于key或者大于key的元素。

那么对应于left==right的情况，检查array\[left\]即可获得key是否存在，若存在则下标为x；

对于left>right的情况，其实是不用考虑的。因为left==上一次循环的mid+1，而mid <= right。若mi+1>right，意味着mid == right，但此时必有left == right，这一轮循环从开始就不可能进入。  
————————————————  
版权声明：本文为CSDN博主「renwotao2009」的原创文章，遵循CC 4.0 by-sa版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/renwotao2009/article/details/51860436

[https_www.cnblogs.com_webary_p_4753231.html]: https://www.cnblogs.com/webary/p/4753231.html
[https_blog.csdn.net_malimingwq_article_details_97418866]: https://blog.csdn.net/malimingwq/article/details/97418866
[https_blog.csdn.net_han_shuai_article_details_75249037]: https://blog.csdn.net/han____shuai/article/details/75249037
[https_blog.csdn.net_renwotao2009_article_details_51860436]: https://blog.csdn.net/renwotao2009/article/details/51860436
[https_www.cnblogs.com_wuyuegb2312_archive_2013_05_26_3090369.html]: https://www.cnblogs.com/wuyuegb2312/archive/2013/05/26/3090369.html#
[https_www.cnblogs.com_moonbay_p_4886799.html]: https://www.cnblogs.com/moonbay/p/4886799.html