📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: tanpf5
跳转到指定楼层
上一主题 下一主题
收起左侧

[二分/排序/搜索] 问一个关于binary search循环跳出条件的问题

🔗
stellari 2016-1-5 16:02:18 | 只看该作者
全局:
binary search其实个人有个人的风格,但是我建议你最好坚持一种原则就好。我说一下我自己的原则:

1、每次收缩left/right时,都保证要找的内容一定在[left, right]范围内这一不变式,根据此原则,即可断定究竟是否用+1/-1,或者不用;

2、根据right和left收缩时+1还是-1,决定mid如何计算。如果是left=mid, 那么计算mid时就取(left + right + 1)/2,否则取(left + right)/2(这是因为后者的mid是偏向左边的,当right-left=1时,left本身就是mid,如果此时用left=mid的话,搜索范围就不会收缩);

3、决定退出条件。做到上述1、2以后,退出条件必定是left<right或者left<=right中的一种。至于是哪种,取决于找到的元素是否一定是正确的元素。比如Search Insert Position这道题,当left=right时,找到的位置必然是可行的位置。这种情况下就不需要再检查了;而如果要看数组中究竟有没有某个元素,那最后缩到范围内只有一个数时,还是要再检查一下,这时就要加上=。

4、如果在循环内返回,那么总是返回mid,如果在循环外返回,永远返回left。循环外除特殊情况外不做判断。当做到1、2、3以后,4一般情况下会自动成立。


比如说,我写First Bad Version(当已经确定有bad version存在的情况下)是这个样子的
int lo = 1, hi = n;
while (lo < hi) {  //  原则3:最后一个找到的一定是bad version,不需要再次判断
    int mid = lo + (hi - lo) / 2;   // 原则2:不存在lo=mid的情况,所以这样就可以,不需+1。
    if (isBadVersion(mid)) hi = mid;   // 原则1:第一个bad version可能在mid之前或mid本身,所以不用mid-1
    else lo = mid + 1;    // 第一个bad version一定在mid之后,所以用mid+1
}
return lo; // 原则4:最后总是返回lo,不做判断。

第1条还有一个变种,就是改成要找的内容一定在“[left, right+1]”这个范围内。这种情况下,退出条件就必须是<=,因为如果用<,且碰巧要找的位置就是right+1,就有可能出现left增大到right时就停止,而不会进一步去找到right+1这个位置。2楼的First Bad Version其实就是采用了这样的原则。这个原则也是可以的,不过我个人只在一种情况下会用这个原则,就是Search Insert Position,因为此时一开始题目就告诉你,最后找到的位置可能会在数组外。这种情况下用这一变种原则显得更自然些。

其实判断退出条件的最好方法是:你列举出当[left, right]范围内剩下2个和3个元素时的所有情况,然后一一验证之。放心,这些情况的总数并不会很多的。

我选择我现在这套原则的理由是:原则1“保证要找的内容一定在[left, right]范围内”这一不变式对我来说很好记。从这一条稍微一推就能推出原则2、3、4。事实证明这套原则最符合我自己的思维方式,让我能很快写出Bug-free的二分法代码。

楼上的一些原则其实都挺好,可能比我说的这一大套更适合你。兼听则明,关键我觉得还是要在结合别人经验的基础上多做题,总结出适合自己的方法。

评分

参与人数 2大米 +15 收起 理由
阿童木 + 10 很有用的信息!
jigsaw_Becky + 5 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
litJordan 2016-1-7 04:52:27 | 只看该作者
全局:
stellari 发表于 2016-1-5 16:02
binary search其实个人有个人的风格,但是我建议你最好坚持一种原则就好。我说一下我自己的原则:

看了这么多感觉大神你的这个总结是最好的!感谢大神的贡献!
回复

使用道具 举报

🔗
jigsaw_Becky 2016-1-7 10:41:52 | 只看该作者
全局:
stellari 发表于 2016-1-5 16:02
binary search其实个人有个人的风格,但是我建议你最好坚持一种原则就好。我说一下我自己的原则:

多做些题发现你这么说真是最有道理的!之前总想用万能的模板,结果发现没有万能的。。。如果不理解,稍微变一下就出错了。。。。
回复

使用道具 举报

🔗
163 2016-1-7 12:13:52 | 只看该作者
全局:
jigsaw_Becky 发表于 2016-1-7 10:41
多做些题发现你这么说真是最有道理的!之前总想用万能的模板,结果发现没有万能的。。。如果不理解,稍微 ...

stellari回复的很好,思维规矩扎实。不过我这里说一个使用+-1的优点(算是有点高阶玩法的意思,当然归根结底,binary search还是很trivial的东西,我就这么一说)

考虑这种情况,数组中前面若干个满足性质f,从某一个开始不满足性质f,如果数组中第0个满足性质f,而最后一个不满足性质f,那么你总可以良定义 “第一个不满足性质f” 或者 “最后一个满足性质f” 的index,
但是如果数组中所有元素都满足性质f,那什么叫做 “第一个不满足性质f” 的index呢?
如果使用非+-1的方法,会返回最大的那个index,这时候你就要判断,如果返回的index是最大index,那么他到底满不满足性质f呢?你就得check一下

如果使用+-1的话,数组中所有元素都满足性质f时,第一个不满足性质f的index返回值就是 n (即v.end()), 也就是说是在最后一个index再往后的一个,这个从数学和逻辑上来说是非常make sense的一件事情,因为这个本身就意味着 “requested index out of bounds”,你可以体会一下。

评分

参与人数 1大米 +5 收起 理由
jigsaw_Becky + 5 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
Mr_DwZ 2016-1-7 13:32:00 | 只看该作者
全局:

一般来说都是用 [a,b) 啦,原因可以看 Dijkstra 大牛写的一个 Draft:https://www.cs.utexas.edu/users/ ... EWD08xx/EWD831.html
我的习惯写法是:
对于区间 [left, right)
mid = (left + right) / 2, 然后区间变成 [left, mid) 或者 [mid, right)。
最后如果只有一个结果,区间一定会变成 [left, left+1)。

其实配合 C++ 的 STL 库的二分查找接口来看,把几个和二分相关的函数看明白,就比较容易理解了。
回复

使用道具 举报

🔗
stellari 2016-1-7 15:14:33 | 只看该作者
全局:
163 发表于 2016-1-7 12:13
stellari回复的很好,思维规矩扎实。不过我这里说一个使用+-1的优点(算是有点高阶玩法的意思,当然归根 ...

确实如此。此时在我31楼的代码中就可以应用原则3,将返回条件由lo < hi 变为 lo <= hi即可,多检查一次,这时代码就和你之前的代码几乎一样了。在我看来,其实“总是使用+1-1”和“按照实际情况决定是否使用+1-1”没有本质区别,只是用了不同的不变式而已。只要最后退出条件不写错,总是能够得到相同的结果的。
回复

使用道具 举报

🔗
 楼主| tanpf5 2016-1-7 15:38:16 | 只看该作者
全局:
Mr_DwZ 发表于 2016-1-7 13:32
一般来说都是用 [a,b) 啦,原因可以看 Dijkstra 大牛写的一个 Draft:https://www.cs.utexas.edu/users/EW ...

你这个思路蛮喜欢的,主要可以处理正好mid就是结果,但是在判断的时候没法判断出来导致low = mid + 1的情况。话说你这个如果可能无解的话能处理吗?
回复

使用道具 举报

🔗
163 2016-1-7 16:28:55 | 只看该作者
全局:
stellari 发表于 2016-1-7 15:14
确实如此。此时在我31楼的代码中就可以应用原则3,将返回条件由lo < hi 变为 lo

你之前的思路很规范,不过我认为你没有理解2楼那种做法的精髓(虽然只有短短几句,谈不上什么高深的思想),2楼那个种手段,亮点就是一次性处理了所有情况,不需要在进入循环前或者跳出循环后做额外的检查,最后返回的version保证一定是想要的结果,请仔细看一遍如下的code,体会一下

int firstBadVersion() {
    int left = 1;
    int right = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}


如果存在[1,n]内的bad version,返回的left一定是第一个bad version的index。如果不存在bad version,则返回的是n+1,也就是说 "All versions are good. The index of the first bad version is over flow"。

你的code需要一个先决条件,也就是 “存在bad version”,在这个前提下,你的code和本楼的code输出结果都一样。

如果不存在bad version,你的code返回的是n,而n不是bad version,这是有问题的。

我说来说去就想强调一点:在不存在bad version的情况下,返回 “n+1”表示 "out of upper bound" 是一个非常自然和合乎逻辑的事情,而本楼的code做到了这一点,不需要任何额外的先决条件。我认为这是有美感在里面的,虽然这段code的二分手段最开始看上去有点 “危险”,不过里面还是有点学问的。
回复

使用道具 举报

🔗
163 2016-1-7 16:31:34 | 只看该作者
全局:
stellari 发表于 2016-1-7 15:14
确实如此。此时在我31楼的代码中就可以应用原则3,将返回条件由lo < hi 变为 lo

另外循环条件是 left <= right 不代表会多检查一次,事实上由于内部总是使用了+-1,所以区间缩短的速度是最快的,事实上在大部分情况下,这种+-1的code需要的总循环次数是最少的。(虽然本质都是log time,聊胜于无吧)
回复

使用道具 举报

🔗
Cici0487 2016-1-7 16:47:25 | 只看该作者
全局:
我一直是用low+1<high的。。。区别这俩条件我记不住
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表