文档章节

当我写二分查找时,我想些什么

我的上铺叫路遥
 我的上铺叫路遥
发布于 2014/02/13 20:25
字数 2033
阅读 4641
收藏 72

两分查找(又称折半查找)是程序员耳熟能详的算法了,不管你用什么语言,不会写简直都不好意思找工作。但我仍然愿意费些笔墨讨论一下这个老生常谈的话题,一方面是自己在网络上看了些资料,温故而知新,另一方面也想借此挑战大众的口味,看看抛砖能否引玉。此处标题稍稍调侃一下诺奖赔率之王村上春树

懒得描述算法了,直接上代码(以下代码都用 C 语言描述,且假设查找对象都是整型数,数组非降序排列),最“经典”的版本:

int binary_search(int *A, int n, int target)
{
    int low = 0, high = n - 1;
    assert(A != NULL && n >= 0);
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if(A[mid] == target)
            return mid;
        else if (A[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

干净利落。一般面试的时候都会考察边界条件迭代、循环终止条件设定以及中位数计算,这里也用了我一向习惯的闭区间设定,即 low 指向数组第一个元素,high 指向数组最后一个元素,当退出循环的时候(没找到),low 大于 high。

当年我也想过,如果用半开半闭区间,那么会增加代码逻辑的复杂性。

int binary_search(int *A, int n, int target)
{
    int low = 0, high = n;
    assert(A != NULL && n >= 0);
    while (low < high)
    {
        int mid = low + (high - low) / 2;
        if (A[mid] == target)
            return mid;
        else if (A[mid] < target)
            low = mid + 1;
        else
            high = mid;
    }
    return -1;
}

注意high是开区间的一端,也就是说A[high]不包含目标值。这样一来,第一,循环条件要改成 low < high,注意写成 low <= high 会死循环的(why?);第二,迭代时 high = mid,而low = mid + 1,因为区间是[low, high),代码写法上不一致。这是容易为人遗漏的一点。

可见开区间比闭区间逻辑上处理麻烦,尤其要提防边界条件迭代和中位数计算可能导致的死循环,算法实现上的差异也在区间的界定上,理论上所有基于中位数二分的算法都会遇到这样的问题。但真的必要用开区间吗?《代码之美》里有一段话:

我们先来考虑循环的执行步骤。假设我们有一个有着 n 个元素的数组(此处n是一个很大的数值),那么从该数组中第一次找到目标的概率为 1/n(一个很小的数值),下一次(经过一次二分)的概率则是 1/(n/2)——仍然不是很大——以此类推下去。事实上,只有当元素的个数减少到了 10 到 20 的时候,一次找到目标的概率才变得有意义,而对于10 到 20 个元素进行查找需要的只是大概 4 次循环。当查找失败时(在大多数的应用中很普遍),那些额外的测试就将变成纯粹的额外开销。

我们也可以来计算一下,在什么时候找到目标值的概率能接近 50%,但请你扪心自问:在一个复杂度为 O(log2N) 的算法中,对于它的每一步都增添一个额外的复杂计算,而目的仅仅是为了减少最后的几次计算,这样做有意义吗?

这段话什么意思呢?归根到底就一个意思,如果一个很大的数组中没有我们想要的目标,那么条件判断 if (A[mid] == target) 完全是一个不必要的开销(分支跳转)。实际上,这种条件只要一次就够了,那就是循环终止并判断最终目标的时候。

给定一个有序(非降序)数组A,可含有重复元素,求最小的i使得A[i]等于target

int binary_search_first_position(int *A, int n, int target)  
{   
    int low = 0, high = n;
    assert(A != NULL && n >= 0);
    while (low < high)
    {
        int mid = low + (high - low) / 2;
        if (A[mid] < target)
            low = mid + 1;
        else // A[mid] >= target
            high = mid;
    }
 
    if (low >= n || A[low] != target)
        return -low - 1;
    else
        return low;
}

我们提出点额外需求,希望目标处于所有重复的匹配项中第一个位置,此时需要返回的下标 low 必须是闭区间一端,不然就没法包含第一位置了。后面的迭代里我们看到,如果目标比 A[mid] 小,闭区间一端 low = mid + 1 就会将 A[mid] 排除在外,反之开区间一端 high = mid。注意我们将相等条件判断包含在 target <= A[mid] 的条件里了,也就是说这种情况下只会移动high,low则一直处于最先位置上保持不动,这样就可过滤掉重复项。根据迭代逻辑,终止条件将是 low == high,如果目标匹配,那么 A[low] 就是第一位置,否则就是不存在。这样一来,循环体中只需用一个 if-else 分支即可。

此外不匹配时的返回值可写成 -low - 1 而不是单纯的 -1,这样调用者一旦发现返回值是负值,那么可以再做一次逆运算,即可获得需要插入新元素的位置,之所以要减 1 是为了避免 low 为 0 时,返回 -low 会被误认为目标存在。

还要注意的是断言写成 assert(n >= 0),防止调用传参时无符号转有符号发生符号扩展正变负,如果 n == 0 表示空数组,那么返回 0 表示需要插入新元素的索引。

给定一个有序(非降序)数组A,可含有重复元素,求最大的i使得A[i]等于target

int binary_search_last_position(int *A, int n, int target)  
{
    int low = -1, high = n - 1;
    assert(A != NULL && n >= 0);
    while (low < high)
    {
        int mid = high - (high - low) / 2;
        if (A[mid] > target)
            high = mid - 1;
        else // A[mid] <= target
            low = mid;
    }
 
    if (high < 0 || A[high] != target)
        return -high - 2;
    else
        return high;
}

反过来,如果目标希望是最后一个位置呢?同理需要返回的下标 high 必须是闭区间一端。这里 low 和 high 的初始值分别为 -1 和 n - 1, mid 迭代改成 mid = high – (high – low) / 2,另外不匹配返回-high - 2(why?)。一来避免出现非法值,二来体现对称性,同时避免产生死循环。

扩展思考,如果给定一个有序(非降序)数组 A,可含有重复元素,求 target 在数组中出现的次数,我们该如何做?

更多内容参考:二分查找问题全集(很多例子可看成上述两例的变种,我对里面的代码做了些修改,仁者见仁)。

更新(2014-02-16):

@programath同学展现了一种循环不变式(loop invariant):如果目标值存在于数组中,那么它的索引必然存在于开区间 (low, high),其中 low + 1 < high,并给出了源代码,这种算法采取完全开区间,好处是消除了闭区间带来的中位数和边界迭代的额外“心智负担”:一来杜绝了迭代死循环,二来不需要像闭区间关注中位数的落点,只要坐落在开区间内即可。我修改了一下:

int binary_search_first_position(int *A, int n, int target)  
{   
    int low = -1, high = n;
    assert(A != NULL && n >= 0);
    while (low + 1 < high)
    {
        int mid = low + (high - low) / 2;
        if (A[mid] < target)
            low = mid;
        else
            high = mid;
    }
 
    if (high >= n || A[high] != target)
        return -high - 1;
    else
        return high;  // high == low + 1
}

int binary_search_last_position(int *A, int n, int target)  
{
    int low = -1, high = n;
    assert(A != NULL && n >= 0);
    while (low + 1 < high)
    {
        int mid = low + (high - low) / 2;
        if (A[mid] > target)
            high = mid;
        else
            low = mid;
    }
 
    if (low < 0 || A[low] != target)
        return -low - 2;
    else
        return low;  // low == high - 1
}


© 著作权归作者所有

我的上铺叫路遥

我的上铺叫路遥

粉丝 84
博文 3
码字总数 8610
作品 4
浦东
程序员
私信 提问
加载中

评论(5)

Lucups
Lucups
楼主年龄几何?
金tangtang
很好
yfwz100
yfwz100
记得是不是编程珠玑提到过这个……
Leon_wy
Leon_wy
写的挺好的
明月照大江
明月照大江
我来了,我来了,我没看文章就先来回帖了,感谢你在酷壳上的投稿,没想到在OSC上也有你的存在,真是太幸运了
二分查找 : 那个隐藏了 10 年的 Java Bug

原文出处:ccmouse 一个偶然的机会,我想起以前还在谷歌上班的时候,有时候大家会在饭桌上讨论最新想出来的一些面试题。在众多有趣又有难度的题目中,有一道老题却是大家都纷纷选择避开的,那...

ccmouse
2017/09/02
0
0
5分钟带你领略:写一个二分查找为什么让面试者挂的这么惨?

二分查找可以说是所有算法中最基础、最容易理解的算法之一了,但事实上也是挂科率最高的考题之一,在各个大厂的应届生面试中,这样的评价屡见不鲜: 谈项目的时候来聊的好好的,叫他写个二分搜...

神三元
09/29
0
0
送书 | 你一定能看懂的算法基础书(代码示例基于Python)

本文引自图灵教育《算法图解》 你一定能看懂的算法基础书;代码示例基于Python;400多个示意图,生动介绍算法执行过程;展示不同算法在性能方面的优缺点;教会你用常见算法解决每天面临的实际...

dqcfkyqdxym3f8rb0
2017/11/24
0
0
递归 —— 二分查找法 —— 归并排序

PS:什么是递归、二分查找、归并排序。 递归排序大家都不陌生,递归简单的说就是自己在没有达到目的的同时在此调用本身,把一个大问题层层转化为和原问题相似的小问题解决,递归需要有边界条...

CMusketeer
2018/07/29
0
0
二分法模板

二分思想:我们对于一个已经排好序的数组,查找某个值的位置(一般为从小到大排序,如为从大到小排序代码会有变动,以下代码均为从小到大排序的代码) 首先最简单的思想肯定是一个for循环扫一...

ZscDst
2017/11/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

JS实现使用Math.random()函数生成n到m间的随机数字

Math.random()函数返回0和1之间的伪随机数,可能为0,但总是小于1,[0,1) 生成n-m,包含n但不包含m的整数: 第一步算出 m-n的值,假设等于w 第二步Math.random()*w 第三步Math.random()*w+n...

张兴华ZHero
26分钟前
4
0
入门了解Service Mesh + Istio?从本文开始

下周六,深圳,阔别已久的线下技术沙龙要和你见面啦! 现场有Rancher Labs研发经理demo刚刚发布的Rancher 2.3中的Istio、Windows容器、集群模板等功能及使用,还有k3s首次线下workshop,由R...

RancherLabs
28分钟前
4
0
Gradle 发布 Jar 到 Archiva 时提示不能 Overwriting released artifacts is not allowed

系统提示错误信息: Received status code 409 from server: Overwriting released artifacts is not allowed. 这是在 Archiva 默认的配置下如果你不是使用 snapshot 配置的话,是不允许对仓...

honeymoose
29分钟前
4
0
二维码插件之qrcode.min.js

文件链接百度云地址 https://pan.baidu.com/s/1nWiBuT4Z7WOAMoUEFL8PZg 入门 http://www.jq22.com/jquery-info294 使用jquery.qrcode.min.js实现前台二维码生成(带Logo) https://blog.csd......

木九天
39分钟前
3
0
开源 java CMS - FreeCMS2.8 自定义标签 commentPage

项目地址:http://www.freeteam.cn/ commentPage 根据参数提取评论对象。 参数 说明 siteid 站点id objtype 评论对象类型 objid 评论对象id membername 会员名称 isanonymous 是否匿名 1是 ...

freeteam
39分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部