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

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

🔗
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上试了的
回复

使用道具 举报

🔗
闲庭听雨 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)你现在这个先排序要慢点。。
回复

使用道具 举报

🔗
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大米 +5 收起 理由
jigsaw_Becky + 5 感谢分享!我去看看!

查看全部评分

回复

使用道具 举报

🔗
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就是了!
回复

使用道具 举报

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

本版积分规则

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