一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2986|回复: 58
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
tanpf5 发表于 2016-1-4 06:49:55 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

评分

1

查看全部评分

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

查看全部评分

回复 支持 7 反对 1

使用道具 举报

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

查看全部评分

回复 支持 6 反对 0

使用道具 举报

Mr_DwZ 发表于 2016-1-7 18:34:56 | 显示全部楼层
本帖最后由 Mr_DwZ 于 2016-1-7 18:54 编辑
tanpf5 发表于 2016-1-7 15:38
你这个思路蛮喜欢的,主要可以处理正好mid就是结果,但是在判断的时候没法判断出来导致low = mid + 1的情 ...

其实这个方法只是自己理解起来方便啦,具体情况具体分析。有多个解和没有解的情况下结果取决于更新区间时的判断条件和更新操作。
STL 里面使用 upper_bound 和 lower_bound 的思路甚是普适,我在刷 OJ 的时候也经常用到~本质上还是返回一个 [a,b)区间,理解更新操作也需要理解区间表达的一致性。
你可以看一下 STL 的实现,感受一下这样没有结果为什么会直接返回 .end()。

http://www.cplusplus.com/referen ... und/?kw=lower_bound

我想表达的是,LZ 不要把某一个写法看成定式,理解了更新区间的本质,在代码实现上就不会再纠结于这些 trivial 的东西啦!




回复 支持 1 反对 0

使用道具 举报

zj45499 发表于 2016-1-4 09:35:46 | 显示全部楼层
本帖最后由 zj45499 于 2016-1-4 09:45 编辑

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

使用道具 举报

闲庭听雨 发表于 2016-1-4 09:43:52 | 显示全部楼层
jigsaw_Becky 发表于 2016-1-4 09:39
你好,除了ls那个turning point in a rotated array,我也还有个类似的问题leetcode 268 missing number
...

你的这个题可以用XOR位运算做。。复杂度只需要O(N)你现在这个先排序要慢点。。
回复 支持 0 反对 1

使用道具 举报

神罗天征 发表于 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
回复 支持 反对

使用道具 举报

jigsaw_Becky 发表于 2016-1-4 09:39:28 | 显示全部楼层
163 发表于 2016-1-4 07:32
这个我有一个很好的方法,是这样的,我认为所有情况下都可以用 left = mid + 1 和 right = mid - 1

并且 ...

你好,除了ls那个turning point in a rotated array,我也还有个类似的问题leetcode 268 missing number
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

答案:(其实是通过binaray search找的index,比如说上面的例子,返回2,就是3 的index, 即nums[2]=3)

Arrays.sort(nums);
        int lo=0;
        int hi=nums.length;
        while(lo<hi){
            int mid=(lo+hi)/2;
            if(nums[mid]>mid){
                hi=mid;
            } else {
                lo=mid+1;
            }
        }      
           return lo;

这个题和楼上那个rotated array,改为while(lo<=hi)      hi=mid-1都不对
请指教!


回复 支持 反对

使用道具 举报

jigsaw_Becky 发表于 2016-1-4 09:43:13 | 显示全部楼层
闲庭听雨 发表于 2016-1-4 09:34
不知道这个能不能套到你的情况里也改成mid+/-1

不能,我在leetcode online judge上试了的
回复 支持 反对

使用道具 举报

jigsaw_Becky 发表于 2016-1-4 09:45:00 | 显示全部楼层
闲庭听雨 发表于 2016-1-4 09:43
你的这个题可以用XOR位运算做。。复杂度只需要O(N)你现在这个先排序要慢点。。

嗯嗯,我知道,谢谢!我看了推荐解法,有3种方法,我都自己再跟着写了一遍
回复 支持 反对

使用道具 举报

闲庭听雨 发表于 2016-1-4 09:47:06 | 显示全部楼层
jigsaw_Becky 发表于 2016-1-4 09:45
嗯嗯,我知道,谢谢!我看了推荐解法,有3种方法,我都自己再跟着写了一遍

恩恩,感觉rotated array是一大类题,都是用Binary search做,但是感觉不太好理解T T 坐等那位大神再来解释一下。。你有做过找turning point of rotated array这道题吗?我觉得是不是直接返回min的index-1就行了啊,因为你如果写出来4,5,6,1,2,3就会发现min和turning point永远是相邻的
回复 支持 反对

使用道具 举报

zj45499 发表于 2016-1-4 10:08:05 | 显示全部楼层
本帖最后由 zj45499 于 2016-1-4 10:13 编辑
jigsaw_Becky 发表于 2016-1-4 09:39
你好,除了ls那个turning point in a rotated array,我也还有个类似的问题leetcode 268 missing number
...

这个题感觉这样写比较好

https://gist.github.com/coderant/05168c48fcce7b7b36d6

二分查找的话题目很多 所以应该用不变应万变的原则.
所以基本是三个原则
  • start + 1 < end
  • 更新首尾的时候, 永远只用 start = mid 和 end = mid
  • 退出循环之后, 验证的顺序要写对


如果遵守了前两条, 那么循环退出之后就会有两个值: 一个 start 一个 end 需要验证.

这个题的话, 把题目改成二分查找的说法就是: 找出第一个 number[index] != index 的数.


所以第三条说的验证顺序, 必须考虑到所有的结束状态, 然后综合结束状态来确认返回值.
应该先验证 start , 如果 start 符合, 就返回.    E.g.: [0,1,2,4,5] start = 3, end = 4.
如果 start 不符合, 再验证 end.                     E.g.: [0,1,2,4,5] start = 2, end = 3.
如果 end 也不符合.                                     E.g.: [0,1,2,3] start = 2, end = 3.

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

jigsaw_Becky 发表于 2016-1-4 10:08:51 | 显示全部楼层
本帖最后由 jigsaw_Becky 于 2016-1-4 10:38 编辑
闲庭听雨 发表于 2016-1-4 09:47
恩恩,感觉rotated array是一大类题,都是用Binary search做,但是感觉不太好理解T T 坐等那位大神再来解 ...

做了,就是你上面回复的那道题吧。这道题他返回的turning point是返回的min的index,比如说[4, 5, 6, 1, 2, 3]中,返回的是3,因为nums[3]=1.你代入算一下就知道了。
我觉得不能返回min的index-1的原因是,有可能这个数组没有rotate,那么你就会返回0-1,就出错了。
这道题后面再用binary search来寻找target的时候,根据target的位置,要么在[4,5,6,1]中进行binary search,要么在[1,2,3]中进行binary search。对于这个时候的binary search就是用的ls的大神讲的第一种方法。我觉得之所以可以直接用[4,5,6,1]进行binary search,对于int mid=(lo+hi)/2,mid会把小数点后面的数字抛弃,所以mid永远不会走到最后那里去。

根据我现在做题,总结的规律就是:
1.和上面大神说的一样,如果有一个target,当nums[mid]==target,就返回的时候,就写成while(lo<=hi)。lo=mi+1.   hi=mid-1
2.没有有一个target,当nums[mid]==target,需要返回的话。即肯定要把这个array全部都进行binary search(比如刚刚你说的rotate point和我说的那个missing number),就用的是while(lo<hi). lo=mid+1. hi=mid

我也很弱,具体为什么我也不清楚,只是看别人答案总结的,有可能因为样本不够大,所以是错误的,欢迎大家批评指正!
回复 支持 反对

使用道具 举报

闲庭听雨 发表于 2016-1-4 10:33:17 | 显示全部楼层

因为6是转折点

本帖最后由 闲庭听雨 于 2016-1-4 10:34 编辑
jigsaw_Becky 发表于 2016-1-4 10:08
做了,就是你上面回复的那道题吧。这道题他返回的turning point是返回的min的index,比如说[4, 5, 6, 1,  ...

不不,你误会了,turning point是另外一道面试题,不是lc上的,不过很像  4,5,6,1,2,3 turning point是6,min是1,所以我觉得两个题返回结果差个1就行了
回复 支持 反对

使用道具 举报

jigsaw_Becky 发表于 2016-1-4 10:37:59 | 显示全部楼层
zj45499 发表于 2016-1-4 10:08
这个题感觉这样写比较好

https://gist.github.com/coderant/05168c48fcce7b7b36d6

start + 1 < end
更新首尾的时候, 永远只用 start = mid 和 end = mid
退出循环之后, 验证的顺序要写对

你好,感觉你这种方法比较好理解,只不过就是不管什么题,都在循环完过后,必须对start和end分别验证。比如[0,1,2,3],target=3,运算完过后,start=2, end=3,这时候end就是我们要的结果。[0,1,2,3],target=0,运算完过后,start=0, end=1,这时候start就是我们要的结果。

我再去体会一下,谢谢啦!
回复 支持 反对

使用道具 举报

jigsaw_Becky 发表于 2016-1-4 10:40:54 | 显示全部楼层
闲庭听雨 发表于 2016-1-4 10:33
不不,你误会了,turning point是另外一道面试题,不是lc上的,不过很像  4,5,6,1,2,3 turning poin ...

哦哦!这样啊!我也认为相差1就是了!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 14:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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