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

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

   
🔗
hhhh27588 2021-11-25 11:48:17 | 只看该作者
全局:
“第二种是我也非常喜欢的二分查找,也就是我最开始说的第一个链接种的那种强大的模板,这种是计算机常用的 [ ) 左开右闭形式”    应该是左闭右开吧?LZ是不是写错了?
回复

使用道具 举报

🔗
 楼主| Falldawn 2021-11-25 12:10:33 | 只看该作者
全局:
hhhh27588 发表于 2021-11-24 19:48
“第二种是我也非常喜欢的二分查找,也就是我最开始说的第一个链接种的那种强大的模板,这种是计算机常用的 ...

是的,写错了,多谢
回复

使用道具 举报

🔗
swole 2021-12-25 01:04:28 | 只看该作者
全局:
wisdompeak2 发表于 2021-4-12 18:06
我强烈推荐的模板其实是 while (left < right)。每一步探索一个mid,如果mid可能是答案,那么把mid保留在下 ...

求问大佬我对这个 while (left < right) 的模版有两个小问题:
1. 对于这个左闭右开区间,[left, right),【什么时候right = n, 什么时候right = n - 1?】
2. 【是否left = mid + 1 , right = mid 和left = mid,right = mid - 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 谢谢

查看全部评分

回复

使用道具 举报

🔗
hhhh27588 2024-3-11 23:20:14 | 只看该作者
全局:
wisdompeak2 发表于 2021-4-12 18:06
我强烈推荐的模板其实是 while (left < right)。每一步探索一个mid,如果mid可能是答案,那么把mid保留在下 ...

我强烈推荐的模板其实是 while (left < right)。每一步探索一个mid,如果mid可能是答案,那么把mid保留在下一次搜索区间,否则把mid排除出下一次搜索区间。

如果这一题无解,需要返回-1,那么这个时候left == right, left 会超出范围, 为什么不推荐while(left <= right)?
回复

使用道具 举报

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

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

使用道具 举报

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

本版积分规则

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