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

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

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
做了一些题然而没想通,啥时候用low<high,什么时候用low<=high

评分

参与人数 1大米 +3 收起 理由
nannnnn + 3 我也一直很疑惑!

查看全部评分


上一篇:Leetcode Wiggle Sort II 求解!还没人给出过O(n)算法。。
下一篇:Java try/catch 作为判断条件使用 求教
推荐
163 2016-1-4 07:32:38 | 只看该作者
全局:
这个我有一个很好的方法,是这样的,我认为所有情况下都可以用 left = mid + 1 和 right = mid - 1

并且这样子code是最高效的,而且看上去十分简洁,

一般binary search 就处理两种情况:
第一种情况:假设数组是按从小到大的顺序排列,从数组v中找一个元素,exactly 和 target相等,那么code是这样(返回 index)

int index(vector<int> v, int target) {
    int left = 0;
    int right = int(v.size()) - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (v[mid] > target) {
            right = mid - 1;
        } else if (v[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}


第二种情况:我们有个性质叫 f, 是用一个函数来表示, f(x) 为真,表示x具有此性质, f(x)为假,表示x不具有此性质,举个例子:f(x) := x > 3 就表示 “x是否>3"这个性质,然后呢?我们需要假设v具有某种二分性质,其中所有满足 f(x)为假的x都在左半边, f(x)为真的都在右半边,现在要求找出 “第一个 f(x)为真的 那个x” (leetcode: first bad version),那么code是这样的:

int index(vector<int> v, int target) {
    int left = 0;
    int right = int(v.size()) - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (f(v[mid])) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

注意这个code处理了所有情况,其中left就是所要求的index,那如果数组中所有元素都满足f(x)为假会怎么样呢?这时候 left最终输出的值就是 数组的size,也就是 v.end() 对应的position,可以理解为 “数组中第一个满足f(x)性质的元素的index是 v.end()”,其实就是说所有v[i] 都不满足性质,是不是非常和谐?哈哈

如果在情况2里面 不使用 +-1, 而用一些类似 right = mid; 这样的东西,那最后还要根据mid的值来判断到底是怎样的情况,code就不elegent了,
另外对于 “找出最后一个不满足 f(x) 性质” 的code,完全可以类似以上情况2去写, 最终结果返回如果是 -1 的话,说明所有v[i]都满足性质。

评分

参与人数 4大米 +23 收起 理由
ohyline + 3 感谢分享!
beer + 10 感谢分享!
闲庭听雨 + 5 回答的很好!
ddvlongren + 5 技术贴,赞!

查看全部评分

回复

使用道具 举报

推荐
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 感谢分享!

查看全部评分

回复

使用道具 举报

推荐
zj45499 2016-1-4 09:35:46 | 只看该作者
全局:
本帖最后由 zj45499 于 2016-1-4 09:45 编辑

永远都用 low + 1 < high 当结束条件 就可以了
循环结束之后判断两个数值 一个 low index 的, 一个 high index 的是否符合你的条件
回复

使用道具 举报

🔗
神罗天征 2016-1-4 07:11:05 | 只看该作者
全局:
搭车同问啥时候 left = mid + 1 和right = mid - 1 or left = mid和right = mid
回复

使用道具 举报

🔗
bbsbbstry 2016-1-4 07:47:28 | 只看该作者
全局:
楼主做leetcode里的first bad version体会一下吧,题不难
回复

使用道具 举报

🔗
闲庭听雨 2016-1-4 08:41:32 | 只看该作者
全局:
163 发表于 2016-1-4 07:32
这个我有一个很好的方法,是这样的,我认为所有情况下都可以用 left = mid + 1 和 right = mid - 1

并且 ...

受益匪浅!大神!
那请问一下对于Search the turing point in a rotated array或者是search the min value in a rotated array又有什么好的办法去理解呢?比如下面这个例子,请大神指点!
public class Solution {
    public int findMin(int[] nums) {
        int start =0, end=nums.length-1;
        while(start<end){
            int mid =(start + end)/2;
            if(nums[mid] > nums[end]){
                    start= mid+1;
            }else{
               
              end= mid;  
            
            }
        }
        
        return nums[start];
        
    }
}
回复

使用道具 举报

🔗
163 2016-1-4 09:28:21 | 只看该作者
全局:
闲庭听雨 发表于 2016-1-4 08:41
受益匪浅!大神!
那请问一下对于Search the turing point in a rotated array或者是search the min val ...

你先给我说这一段code是干啥呢?
回复

使用道具 举报

🔗
闲庭听雨 2016-1-4 09:33:00 | 只看该作者
全局:
163 发表于 2016-1-4 09:28
你先给我说这一段code是干啥呢?

是找一个rotated array里面的最小值,leetcode上的题,也是二分查找做的
回复

使用道具 举报

🔗
jigsaw_Becky 2016-1-4 09:33:55 | 只看该作者
全局:
闲庭听雨 发表于 2016-1-4 08:41
受益匪浅!大神!
那请问一下对于Search the turing point in a rotated array或者是search the min val ...

我也正想问这个问题!!!!
回复

使用道具 举报

🔗
闲庭听雨 2016-1-4 09:34:37 | 只看该作者
全局:
163 发表于 2016-1-4 09:28
你先给我说这一段code是干啥呢?

不知道这个能不能套到你的情况里也改成mid+/-1
回复

使用道具 举报

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

本版积分规则

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