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

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

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

十分感谢你的耐心回答!
我在leetcode上找了几道binary search的题,分别用你和stellari的方法试了一下,都没有出错了,太开心了!终于弄明白了!thanks~~~~
回复

使用道具 举报

🔗
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 的东西啦!




回复

使用道具 举报

🔗
163 2016-1-7 21:36:35 | 只看该作者
全局:
Mr_DwZ 发表于 2016-1-7 18:34
其实这个方法只是自己理解起来方便啦,具体情况具体分析。有多个解和没有解的情况下结果取决于更新区间时 ...

这个很不错。不过个人认为这里有个细节值得注意一下,那就是c/c++的整数除法是下取整的,也就是说 (1 / 2) == 0,这个在这种 [left, right) 的处理方式中起到了不可或缺的作用,
试想如果right == left + 1, 并且 right是end position,而整数除法是通常的四舍五入round-off的话,那么mid 就会取到right,直接导致access (*mid), 这是个 undefined operation.
回复

使用道具 举报

🔗
stellari 2016-1-8 08:50:33 | 只看该作者
全局:
163 发表于 2016-1-7 16:28
你之前的思路很规范,不过我认为你没有理解2楼那种做法的精髓(虽然只有短短几句,谈不上什么高深的思想 ...

抱歉,不过我想你可能没看清我上面一楼。我的意思是“如果不确定存在bad version时,只要把我代码中的lo<hi改成lo<=hi就行”,结果返回的就是n+1,和你的代码是一样的。因为不存在bad version时,一定lo是一直增加,而hi不动。这时我们的code中每次执行的都是lo = mid + 1,所以会得到完全一样的结果。

你的意思我完全理解,我们写的代码的理念也是完全一样的:“没有做任何额外检查,保证一定是想要的(且符合逻辑的)结果,保证具有一定的编程美学在里面”。事实上,我一开始写二分法时,就是用的你的写法。后来觉得现在这种风格更适合我,就换过来了。但是,这两种方法区别仅在于原则1稍有不同,最后结果是可以做到完全一样的。
回复

使用道具 举报

🔗
163 2016-1-8 09:02:44 | 只看该作者
全局:
stellari 发表于 2016-1-8 08:50
抱歉,不过我想你可能没看清我上面一楼。我的意思是“如果不确定存在bad version时,只要把我代码中的lo

你把 lo < hi 改成 lo <= hi 会出bug的,
只要有bad version,就是死循环,你自己体会一下。
回复

使用道具 举报

🔗
163 2016-1-8 09:06:29 | 只看该作者
全局:
stellari 发表于 2016-1-8 08:50
抱歉,不过我想你可能没看清我上面一楼。我的意思是“如果不确定存在bad version时,只要把我代码中的lo

你之前那个总结写的很好。

我说的这种方法,并不是适用所有能用binary search做的算法,比如好像有个叫 “找peak number”的题,我这么搞就是不行的。peak number就是说一个number不小于他左边和他右边 (index -1 和 n 默认是 -\infty )
因为peak number不一定是连续一段出现,所以我的手段就失效了。不过用你的方法,还是能锁定至少一个peak number在所搜索的区间内的。
回复

使用道具 举报

🔗
stellari 2016-1-8 09:10:09 | 只看该作者
全局:
163 发表于 2016-1-8 09:02
你把 lo < hi 改成 lo

啊哈!多谢指出,这才是问题的关键。抱歉我之前光是想着你说的那种不存在bad version的情况,忽略了检查代码的正确性。
回复

使用道具 举报

🔗
stellari 2016-1-8 09:53:57 | 只看该作者
全局:
163 发表于 2016-1-8 09:06
你之前那个总结写的很好。

我说的这种方法,并不是适用所有能用binary search做的算法,比如好像有个 ...

多谢多谢、另外顺带一提,我之前说的那个<改成<=的方法其实是不符合我的原则的,刚才没想清楚。按照我的原则1,“保证要找的元素一定在[lo, hi]之间”,所以当不能保证bad version出现时,lo和hi应该分别初始化为0和n,而非0和n-1。退出条件<号不改,这下应该就行了。
回复

使用道具 举报

🔗
163 2016-1-8 09:59:50 | 只看该作者
全局:
stellari 发表于 2016-1-8 09:53
多谢多谢、另外顺带一提,我之前说的那个

嗯,这是可以的。
这也是楼上某位贴的STL里面的标准处理方法。
回复

使用道具 举报

🔗
jigsaw_Becky 2016-1-8 11:17:55 | 只看该作者
全局:
本帖最后由 jigsaw_Becky 于 2016-1-8 11:26 编辑

这几天看了上面几位大神的讨论,总算把binary search 弄清楚了

在leetcode上看到一道题,感觉能很好的体现楼上2位大神(stellari和163)说的思想,我分别试了一下(也看了discussion滴),都Acceptted了,写出来希望对后面的人理解有帮助

34. Search for a Range ( https://leetcode.com/problems/search-for-a-range/ )
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

//solution 1
public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int lo=0;
        int hi=nums.length-1;
        int[] result={-1,-1};
        while(lo<hi){
            int mid=(lo+hi)/2;
            if (nums[mid]<target){
                lo=mid+1;
            } else {
                hi=mid;
            }
        }
        if(nums[lo]!=target){
            return result;
        }
        result[0]=lo;
        hi=nums.length-1;
        while(lo<hi){
            int mid=(lo+hi)/2+1;
            if(nums[mid]>target){
                hi=mid-1;
            } else {
                lo=mid;
            }
        }
        result[1]=lo;
        return result;
    }
}

// solution 2
public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result={-1,-1};
        int lo=0;
        int hi=nums.length-1;
        while(lo<=hi) {
            int mid=(lo+hi)/2;
            if(nums[mid]<target){
                lo=mid+1;
            } else {
                hi=mid-1;
            }
        }
       //第一个while循环结束过后,lo的值就是target应该在的位置。如果nums=[1],target=0,则lo=0.如果nums=[0],target=1,则lo=1。所以下面的判断条件就有2种情况。
        if(nums.length==lo||nums[lo]!=target){
            return result;
        }
        result[0]=lo;
        hi=nums.length-1;
        while(lo<=hi){
            int mid=(lo+hi)/2;
            if(nums[mid]==target){
                lo=mid+1;
            } else {
                hi=mid-1;
            }
        }
        result[1]=lo-1;
        return result;
    }
}


回复

使用道具 举报

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

本版积分规则

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