你好,游客 登录 注册 搜索
背景:
阅读新闻

二分查找真的有你想象中那么简单吗?

[日期:2015-08-24] 来源:Linux社区  作者:webary [字体: ]

  二分查找是查找算法里家喻户晓的算法了,其时间复杂度为O(logn),可是如果真的让你立马拿出笔写一个二分查找的函数出来,你确定你可以比较快的完全写对吗?

  我们的目的是从一个已经按从小到大的顺序排序好的数组arr中查找值为value的元素的位置。

  大体思路我们应该都很清楚:有三个游标,一个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;
}

这个模板函数可以接受不同类型的数组,当然为了兼容C++ STL中的vector容器,又对参数做了小小的改进!

时间仓促,如果内容上有什么疑问或者错误之处,请指出,谢谢!

Golang二分查找算法的简单实现 http://www.linuxidc.com/Linux/2014-02/96093.htm

二分查找改进版 http://www.linuxidc.com/Linux/2013-10/91721.htm

二分查找的实现及注意事项 http://www.linuxidc.com/Linux/2013-07/87308.htm

用Python实现二分查找 http://www.linuxidc.com/Linux/2012-12/75948.htm

二分查找之Java实现 http://www.linuxidc.com/Linux/2012-05/59869.htm

Java针对数组的普通查找法和二分查找法 http://www.linuxidc.com/Linux/2012-03/57065.htm

本文永久更新链接地址http://www.linuxidc.com/Linux/2015-08/122173.htm

linux
相关资讯       二分查找 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款