再谈Binary Search 模板while (left < right)的理解

苹果用户_skswv 发表于 2024-5-3 08:45
之前都是在背模版，经常写错，后面看labuladong的二分模版讲解，理解了不少，会觉得他那样左闭右闭加上用

对，仔细理解为啥写怎么写就不会出错了。<= 那种最不喜欢的，因为最后不知道返回啥，所以一般需要过程用一个结果来记录，当然这样也是可以的。

我觉得纠结小于还是小于等于就已经跑偏了，ls有层主提到了建模过程我推荐这篇文章 https://tylerhou.com/posts/binary-search-with-confidence/（似乎和ls提到的bili视频是类似思路）

我自己preferred的做法（在这篇blog基础上改进）是把initial left and right设成-1和array length（想象有俩virtual element）分别是绿跟红，然后每次取中值的时候更新红绿区间，好处是不需要进行bounds check（null check工作中一般会直接enforce non-null或者静态infer nullity没必要特殊处理），但是constant factor less efficient。

多金的大白鹅 发表于 2024-5-3 10:53
我觉得纠结小于还是小于等于就已经跑偏了，ls有层主提到了建模过程我推荐这篇文章 https://tylerhou.com/po ...

完全没有纠结啊，<=也可以，但是你要用一个result来记录就可以啦

3种写法都可以，具体是的知道为什么这么写，我就是分享一下我的总结，这样也能看懂别人写的代码。否则用任何一种都可以

Falldawn 发表于 2024-5-3 11:33
左右边界为0和n-1显然不对，答案对了是因为没有提供完整的测试案例，不信你可以试试https://leetcode.com ...

不是，哥们。帖子说讨论的是通用的情况，我不知道你说的是哪题，所以前提是“值域是0到n-1的话”（所有可能的解组成的连续单调的空间）。你给的这题，搜索的空间不是1到n-2或者2到n-1吗（取决于你怎么分割）😓

补充：类似这题2790 Maximum Number of Groups With Increasing Length，搜索的空间不是0到n-1而是1到n，或者这题2141. Maximum Running Time of N Computers搜索的空间是0到电池电量平均数，都不妨碍我贴的那个找右端点写法是对的。

SoWhat0309 发表于 2024-5-3 11:11
不是，哥们。帖子说讨论的是通用的情况，我不知道你说的是哪题，所以前提是“值域是0到n-1的话”（所有可 ...

取决用你用 left < right 还是left < right - 1还是left <= right啊

如果你用 left < right，而且mid = left + (right - left) / 2，那么mid为了覆盖[0, n)，left 和right必须初始化成0和n

如果你用 left < right，而且mid = right - (right - left) / 2，那么mid为了覆盖[0, n)，left 和right必须初始化成-1和n - 1

Falldawn 发表于 2024-5-3 14:19
取决用你用 left < right 还是left < right - 1还是left

没记错的话，用left < right，mid = left + (right - left+1) / 2利用division truncation就可以避免死循环了，没必要把一个不可能是解的-1包括进搜索的范围（除非最后要通过这个不可能的值判断解是否存在）。

SoWhat0309 发表于 2024-5-3 11:30
没记错的话，用left < right，mid = left + (right - left+1) / 2利用division truncation就可以避免死循 ...

这个不是记的问题，是理解的问题，你搜索的不是left和right而是mid，因为你mid偏右，所以left必须设为-1才可以保证mid有可能为0，那就是left = -1, right = 0时，不然你怎么可能搜索到0？

要不然为啥mid偏左的时候为啥初始化left = 0, right = n？

我的帖子就是为了说明这个啊

Falldawn 发表于 2024-5-3 14:44
这个不是记的问题，是理解的问题，你搜索的不是left和right而是mid，因为你mid偏右，所以left必须设为-1 ...

理解就是用left < right循环的话，每次解空间减半最终只剩一个，要么这是最终的解，要么这是值域外的解代表解不存在。我说记是指leetcode这网站上写过的二分题目的印象，你为什么会觉得我在死记模板呢？说搜不到0，你可能没看到贴出来mid的取法……

SoWhat0309 发表于 2024-5-3 11:51
理解就是用left < right循环的话，每次解空间减半最终只剩一个，要么这是最终的解，要么这是值域外的解代 ...

mid能有几种取法？没有说你记模板啊，但是我已经说明了为啥mid右偏的时候left = -1, right = n - 1，而不是其他值，因为搜索的是mid而不是left和right

Falldawn 发表于 2024-5-3 14:58
mid能有几种取法？没有说你记模板啊，但是我已经说明了为啥mid右偏的时候left = -1, right = n - 1，而不 ...

一开始就贴出来的，mid = (left + right + 1)/2啊。利用除法向上向下取整，结果不就是所谓的右偏吗？如果用left < right的话，搜的也不是什么left，right，mid，而是最后搜索空间剩下的那个唯一的解吧？