查看: 4582|回复: 31
收起左侧

[二分/排序/搜索] 关于Binary Search的疑惑

  |只看干货
RELAY2014 | 显示全部楼层 |阅读模式
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (85)
 
 
0% (0)    👎

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

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

x
最近在刷BS这个Tag,感觉就是提都不难,但是关于boundary 的设定就是有点搞不明白。
int left = 0, right = nums.length;
有时又看到,right = nums.length -1;
while loop里,有时left < right 有时left <=right ;
关于pivot/mid 有时用 mid = left + (right - left) /2 有时又 mid = (left + right) /2;
.......
感觉又好复杂,
求大牛指点迷津。

评分

参与人数 4大米 +8 收起 理由
kasumijay + 2 很有用的信息!
milkncookie + 2 给你点个赞!
大橙子的世界 + 1 赞一个
14417335 + 3

查看全部评分


上一篇:刷题求建议,我目前的水平阶段刷什么题更好一点?
下一篇:请问leecode老版本回不去了么?
红A 2021-7-13 02:26:06 | 显示全部楼层
本楼: 👍   100% (28)
 
 
0% (0)   👎
全局: 👍   89% (3936)
 
 
10% (479)    👎
while loop板子有3个
left <= right, left = mid + 1, right = mid - 1;
left + 1 < right, left = mid, right = mid;
left < right, left = mid + 1, right = mid;

mid = left + (right - left) / 2是为了防止integer越界

评分

参与人数 6大米 +6 收起 理由
hpyomuannd + 1 赞一个
枫子吟 + 1 赞一个
佛系咸鱼 + 1 给你点个赞!
wsrrzxl + 1 赞一个
大橙子的世界 + 1 赞一个
skuani + 1 赞一个

查看全部评分

回复

使用道具 举报

smallwarm 2021-7-13 05:59:49 | 显示全部楼层
本楼: 👍   100% (15)
 
 
0% (0)   👎
全局: 👍   96% (191)
 
 
3% (6)    👎
这样说吧,我给你三个模板
1. 当你需要找一个特定值
  1. int l = 0, r = nums.length - 1;
  2. while (l <= r) {
  3.         int mid = l + (r-l) / 2;
  4.         if (arr[mid] == target)  {
  5.             return mid;
  6.         } else if (arr[mid] > target) {
  7.             r = mid - 1;
  8.         } else {
  9.             l = mid + 1;
  10.         }
  11. }
复制代码



2.  找下界(第一次出现)
  1.     int l = 0, r = nums.length - 1;
  2.     while (l < r) {
  3.         int mid = l + (r-l) / 2;
  4.         if (nums[mid] >= target) {
  5.             // 满足条件的时候,把右边界设成mid,这样右边不断向**近,直到第一次出现
  6.             r = mid;
  7.         } else {
  8.             // 不满足的时候,移动左边
  9.             l = mid + 1;
  10.         }
  11.     }
复制代码




3. 找上界(最后一次出现)
  1.     int l = 0, r = nums.length - 1;
  2.     while (l < r) {
  3.         // 注意!向右逼近的时候, mid 后面要+1,不然会死循环
  4.         int mid = l + (r-l) / 2 + 1;
  5.         if (nums[mid] <= target) {
  6.             // 满足条件的时候,把左边界设成mid,这样不断向右逼近,直到最后一次出现
  7.             l = mid;
  8.         } else {
  9.             // 不满足的时候,移动右边
  10.             r = mid - 1;
  11.         }
  12.     }
复制代码





模板题 lc 34. Find First and Last Position of Element in Sorted Array
```
public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }

        // binary search to find first
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r-l) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        int first = l;
        if (nums[first] != target) {
            return new int[]{-1, -1};
        }

        l = 0; r = nums.length - 1;
        while (l < r) {
            int mid = l + (r-l)/2 + 1;
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return new int[]{first, l};
    }   
```

评分

参与人数 5大米 +11 收起 理由
zenas_ + 1 赞一个
pikailun + 2 很有用的信息!
lee2009jian + 3 很有用的信息!
kasumijay + 2 很有用的信息!
jliu + 3 很有用的信息!

查看全部评分

回复

使用道具 举报

cute_susu_bobo 2021-7-14 00:43:51 | 显示全部楼层
本楼: 👍   100% (4)
 
 
0% (0)   👎
全局: 👍   97% (288)
 
 
2% (6)    👎
Leetcode 上面有一个很好的帖子, google直接搜leectode binary search 101
第一个就是
讲的特别好,看完之后binary search从此没烦恼

评分

参与人数 2大米 +3 收起 理由
pikailun + 2 很有用的信息!
大橙子的世界 + 1 赞一个

查看全部评分

回复

使用道具 举报

古城 2021-7-13 02:29:18 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (155)
 
 
0% (0)    👎


字数字数

评分

参与人数 1大米 +2 收起 理由
wytwyt + 2 看过你的视频,很有用

查看全部评分

回复

使用道具 举报

redhairdragon 2021-7-13 03:19:52 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (2117)
 
 
2% (59)    👎
我也是挺烦这些的, 谷歌binary search template 读一下第一篇, 背个template做做习题练一下就好了
回复

使用道具 举报

Tktticket 2021-7-13 03:23:34 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (360)
 
 
2% (10)    👎
不同模板无非是为了不造成无限循环,你可以根据code反推当left和right相近的时候的情况会不会无限循环
也有先把最后结果是right/left的情况处理再往那边靠近的,需要根据while内部的逻辑而定
回复

使用道具 举报

xirideqinwen200 2021-7-13 03:54:26 | 显示全部楼层
本楼: 👍   0% (0)
 
 
100% (1)   👎
全局: 👍   88% (189)
 
 
11% (25)    👎
binary search 最简单了,只需要search一头,抛弃另一头
回复

使用道具 举报

Liyukuang 2021-7-13 05:13:15 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (1856)
 
 
1% (28)    👎
我也有过这个疑惑,解决方案是永远只用 while left <= right
更新的时候要么是left=mid+1,要么right=mid-1, 这样就会避免无限循环。一旦找到满足条件的用个变量result暂时保存起来。返回时候看看result是不是曾经找到过。这样同一个模板可以解决找到相等,小于,大于这些不同情况

补充内容 (2021-07-13 05:29 +08:00):
比如找sorted list里面小于x的最大的数
Ans = None

While left <= right:
       Mid = left + (right - left) // 2
       If list[mid] < x:
              Ans = list[mid]
              Left = mid + 1
       Else:
              Right = mid - 1
Return Ans if ans is not none else exception


找相等的
While left <= right:
       Mid = left + (right - left) // 2
       If list[mid] == x:
              Ans = list[mid]
              Left = mid + 1
       Else:
              Right = mid - 1
Return Ans if ans is not none else exception
回复

使用道具 举报

kunomukou 2021-7-13 07:31:18 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (110)
 
 
0% (1)    👎
不同人给你不同的模板然后你就又晕了。最终最好选一个自己的模板。
我是用的是c++的lower bound来记,永远都是左闭右开,left + ((right - left) >> 1)取中间值。好处是
1. 需要记的模板代码少;
2. left永远都是起始的index,right - left永远都是当前区间的长度。

知乎上搜这个很详细“二分查找有几种写法?它们的区别是什么?”感谢Dijkstra!
回复

使用道具 举报

我是你哥哥 2021-7-13 08:40:30 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (113)
 
 
2% (3)    👎
回复

使用道具 举报

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

本版积分规则

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