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

[二分/排序/搜索] Binary Search for Beginners,最不易出错的 Binary Search写法和总结

   
全局:

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

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

x
本帖最后由 Falldawn 于 2021-4-13 01:27 编辑

前面有junior147147 已经发了一篇关于二分查找的总结贴了
[二分/排序/搜索] Binary Search的总结帖


楼主写得很好,但是我感觉大家可以参考以下几个链接https://leetcode.com/discuss/general-discussion/786126/Python-Powerful-Ultimate-Binary-Search-Template.-Solved-many-problems
https://segmentfault.com/a/1190000016825704
https://leetcode.com/problems/binary-search/discuss/423162/Binary-Search-101-The-Ultimate-Binary-Search-Handbook
https://leetcode.com/explore/learn/card/binary-search/

但是呢这上面总结得还是不够全面,对于新手来说,最好最不容易出错的就是while (left < right - 1)

  1. int left = 0;
  2. int right = nums.length - 1;
  3. while (left < right - 1) {
  4.     int mid = left + (right - left) / 2;
  5.     if (condition) {
  6.         left = ?;
  7.     } else {
  8.         right = ?;
  9.     }
  10. }
复制代码



然后再后续单独处理剩下的2个元素

为什么?因为退出while循环的条件是left +1 = right,也就是最后有2个元素时才退出,这样就保证了不可能出现死循环。写代码的时候只要注意移动left和right的时候不要错过最后的答案就可以了,这种方法对于初学者是最好的,而且非常适合对于处理重复元素的题目。大家可以试一试一下Leetcode上的Shifted/Rotated Sorted Array Problems,如果是会员,则考虑做一下302题,相信你对二分查找一定上了一个台阶。

33. Search in Rotated Sorted Array
81. Search in Rotated Sorted Array II
154. Find Minimum in Rotated Sorted Array II
1095. Find in Mountain Array
302. Smallest Rectangle Enclosing Black Pixels


第二种是我也非常喜欢的二分查找,也就是我最开始说的第一个链接种的那种强大的模板,这种是计算机常用的 [ ) 左开右闭形式,有好处,比如直接算长度的时候那就是[left., right) = right - left,用途非常广泛,什么时候使用这种模板呢?一般是不需要循环中返回值而是退出循环后返回值的情况。

  1. int left = 0;
  2. int right = nums.length;
  3. while (left < right) {
  4.     int mid = left + (right - left) / 2;
  5.     if (nums[mid] < target) {
  6.         left = mid + 1;
  7.     } else {
  8.         right = mid;
  9.     }
  10. }
复制代码



二分查找的高级用法:只要有一个条件可以把搜索空间减半,就可以使用二分查找。请考虑使用以上2种二分法做一下Leetcode题目

1011. Capacity To Ship Packages Within D Days        31
1482. Minimum Number of Days to Make m Bouquets        34
875. Koko Eating Bananas        36
1231. Divide Chocolate        38
668. Kth Smallest Number in Multiplication Table        40
719. Find K-th Smallest Pair Distance        42
786. K-th Smallest Prime Fraction        44
774. Minimize Max Distance to Gas Station        48
644. Maximum Average Subarray II        51
410. Split Array Largest Sum        53

标准的二分查找如下,退出循环条件是left <= right,也就是说最后只有一个元素时也进入循环,这就有个问题,移动left和right时必须要+1和-1,要不然就可能出现死循环,比如只有1个和2个元素时。什么时候适合用标准的二分查找呢?那就是你需要在循环内返回值的情况,比如找具体某个值时。

  1. int left = 0;
  2. int right = nums.length - 1;
  3. while (left <= right) {
  4.     int mid = left + ((right - left) >> 1);
  5.     if (nums[mid] == target) return mid;
  6.     else if (nums[mid] > target) {
  7.         right = mid - 1;
  8.     } else {
  9.         left = mid + 1;
  10.     }
  11. }
  12. return -1;
复制代码






评分

参与人数 24大米 +34 收起 理由
达达万 + 1 赞一个
figwd2347 + 1 赞一个
烤馒头 + 1 赞一个
kafkagre + 1 给你点个赞!
YouranLee + 1 很有用的信息!

查看全部评分


上一篇:为何需要Bean的后置处理器?
下一篇:Longest Substring Without Repeating Characters - Optimized Brutal Force Solution

本帖被以下淘专辑推荐:

推荐
wisdompeak2 2021-4-13 07:06:05 | 只看该作者
全局:
本帖最后由 wisdompeak2 于 2021-4-13 07:10 编辑

我强烈推荐的模板其实是 while (left < right)。每一步探索一个mid,如果mid可能是答案,那么把mid保留在下一次搜索区间,否则把mid排除出下一次搜索区间。
这样退出的时候必有left==right。如果这题有解,那么收敛解一定就是最终解,不用double check你的结果。



评分

参与人数 3大米 +4 收起 理由
beer + 2 很有用的信息!
头头826 + 1 很有用的信息!
咸鱼上岸 + 1 赞一个

查看全部评分

回复

使用道具 举报

推荐
wisdompeak2 2021-12-25 01:17:12 | 只看该作者
全局:
swole 发表于 2021-12-24 09:04
求问大佬我对这个 while (left < right) 的模版有两个小问题:
1. 对于这个左闭右开区间,[left, right) ...

你理解错了,这个模板是双闭区间。每个回合内, [left, right]都有可能是答案。

我之前说过,你选择一个mid,只要mid一定不可能是答案,那么就把它排除在下一回合呢,即left=mid+1(对应right=mid),或者right=mid-1(对应left=mid),根据你的题意而定(排除上半区间或是下半区间)。

选择mid的写法有两种 mid = left+(right-left)/2,或者mid=right-(right-left)/2,两者只相差一位。选择哪种写法取决于你后面的二分写法。原则就是不能出现死循环。判断的时候很方便,你令left=0,right=1,如果发现下一轮的区间依然是[0,1],那么你的mid写法就错了,换另一种就行。
比如:
  1. while (left < right)
  2. {
  3.   int mid = left+(right-left)/2; // 这行先随便写,之后会修改
  4.   if (checkOK(mid))
  5.      left = mid;
  6.   else
  7.     right = mid-1;
  8. }
  9. return left; // 如果此题一定有解,那么收敛解就是最优解
复制代码
这段代码你写完之后检查,发现代入[0,1]后这题有死循环的问题(永远停在[0,1]而不收敛),于是无脑改写为另一种写法mid=right-(right-left)/2即可。

评分

参与人数 1大米 +1 收起 理由
swole + 1 谢谢

查看全部评分

回复

使用道具 举报

推荐
 楼主| Falldawn 2024-5-3 01:10:29 | 只看该作者
全局:
hhhh27588 发表于 2024-3-11 08:20
我强烈推荐的模板其实是 while (left < right)。每一步探索一个mid,如果mid可能是答案,那么把mid保留在 ...

因为left <= right后经常不知道到底该返回哪一个值
回复

使用道具 举报

🔗
qldx 2021-4-13 07:04:29 | 只看该作者
全局:
喜欢第二种,很少出错,只有在最讨厌的比如rotate array等需要细细处理的情况才会考虑左右都是闭区间。

那个高级用法第一次遇到的时候简直震惊了,后来就慢慢适应了,可以找到这种题型与二分法的规律,比如有单调性,比如是在求满足某个复杂条件的临界值
回复

使用道具 举报

🔗
 楼主| Falldawn 2021-4-13 08:02:50 | 只看该作者
全局:
wisdompeak2 发表于 2021-4-13 07:06
我强烈推荐的模板其实是 while (left < right)。每一步探索一个mid,如果mid可能是答案,那么把mid保留在下 ...

我也是用这个最多,对于出现重复值的情况考虑第一种
回复

使用道具 举报

🔗
whodatj 2021-4-13 11:27:34 | 只看该作者
全局:
马克马克马克
回复

使用道具 举报

全局:
赞 马克马克
回复

使用道具 举报

🔗
gongliheng 2021-4-13 14:49:28 | 只看该作者
全局:
计算机科学家!👩‍🔬
回复

使用道具 举报

全局:
mark!计算机科学家!
回复

使用道具 举报

🔗
开心的猪 2021-4-18 06:47:33 | 只看该作者
全局:
楼主,你的帖子真是非常好,就是有python版本就更好了
回复

使用道具 举报

🔗
 楼主| Falldawn 2021-4-18 07:03:23 | 只看该作者
全局:
开心的猪 发表于 2021-4-18 06:47
楼主,你的帖子真是非常好,就是有python版本就更好了

多谢多谢!我好久不用Python,其实刷题还是建议Java好一些,Python太高级了,看起来没那么清晰
回复

使用道具 举报

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

本版积分规则

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