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

SoWhat0309 发表于 2024-5-3 12:05
一开始就贴出来的，mid = (left + right + 1)/2啊。利用除法向上向下取整，结果不就是所谓的右偏吗？如果 ...

mid = (left + right + 1)/2就是往右偏，和mid = right - (right - left) / 2一样，那么mid为了覆盖[0, n)，left 和right必须初始化成-1和n - 1，不然（如果你初始化为0和n - 1）你mid搜索不到0这个index。

同样的道理

mid = (left + right)/2就是往左偏，和 left + (right - left) / 2一样，那么mid为了覆盖[0, n)，left 和right必须初始化成0和n，不然（如果你初始化为0和n - 1）你mid搜索不到你 n - 1这个index。

如果你用 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 15:13
mid = (left + right + 1)/2就是往右偏，和mid = right - (right - left) / 2一样，那么mid为了覆盖[0, n ...

有没有一种可能，我贴那个取法真能搜到0（或者最左边界）呢？还是说Leetcode这个网站上二分的题目test case绝大部分都有问题，不小心让我几乎全过了呢？

一个例子 2790. Maximum Number of Groups With Increasing Length，解的取值范围是1到n，我完全没有必要把左边界设置成0（如果解在边界内一定存在的话），或者34. Find First and Last Position of Element in Sorted Array，因为解可能不存在，所以视边界条件可能需要判断。

另外“left 和right必须初始化成0和n，不然（如果你初始化为0和n - 1）你mid搜索不到你 n - 1这个index”这结论明显是不对的，无论你怎么偏，mid都是可能取到左右边界内每一个值的（题目一大把懒得找了）。加上一个不可能的n，更可能的目的是0到n-1内所有点都不满足条件，最后到n表示解不存在。

SoWhat0309 发表于 2024-5-3 12:05
一开始就贴出来的，mid = (left + right + 1)/2啊。利用除法向上向下取整，结果不就是所谓的右偏吗？如果 ...

直接上个例子吧，

找一个数组A中 < 4的最大值的index

如果A = {4， 5， 6}，初始化left = 0, right = n - 1 = 2，

mid = （left + right + 1）/ 2 = 2, A[2] >= 4, right = mid - 1 = 1

left = 0, right = 1, mid = 1, A[1] >= 4, right = mid - 1 = 0

left = 0 = right , stop and return left which is 0

这时发现mid = 0这个index没有检查

SoWhat0309 发表于 2024-5-3 12:27
有没有一种可能，我贴那个取法真能搜到0（或者最左边界）呢？还是说Leetcode这个网站上二分的题目test ca ...

你说的对，leetcode上题目几乎都能过，你可以继续使用，我只是说明了为什么那么初始化的原因，因为搜索的是mid

SoWhat0309 发表于 2024-5-3 12:27
有没有一种可能，我贴那个取法真能搜到0（或者最左边界）呢？还是说Leetcode这个网站上二分的题目test ca ...

那能问一下，为什么初始right化为n呢？为啥不初始化成n - 1

Falldawn 发表于 2024-5-3 15:34
直接上个例子吧，

找一个数组A中 < 4的最大值的index

你这是不确定最后解是否在边界内存在的情况，看我最后一句话。你这个情况最后剩下一个0，因为不确定解是不是在搜索空间内存在最后需要多判断一步。加上一个-1算一种偷懒的做法，因为如果0到n-1内所有值都不符合条件，最后收敛到-1这个不可能的值，表示解不存在。

Falldawn 发表于 2024-5-3 15:36
那能问一下，为什么初始right化为n呢？为啥不初始化成n - 1

同样楼上的道理，很多时候初始化加上一个n配合left < right是可能收敛到n的，但这不表示最后解是n而是表示解不存在。你的帖子我好歹是认真看过+贴出来的题目做过才发表看法的，至于你后面太长不看、“啊对对对”回复的心态，我就不懂了。

Falldawn 发表于 2024-05-03 12:34:02
直接上个例子吧，

找一个数组A中 < 4的最大值的index

为啥要  left +right +1？ 直接left +right不就能取到0了吗？

SoWhat0309 发表于 2024-5-3 12:39
你这是不确定最后解是否在边界内存在的情况，看我最后一句话。你这个情况最后剩下一个0，因为不确定解是 ...

你可以说是偷懒，简单一句话总结，就是如果初始化为0和n - 1并且mid右偏的前题条件是这个解一定在[0, n)中，那解是有可能不存在啊？leetcode上给出的全部是解在的情况

djmiss 发表于 2024-5-3 12:41
为啥要  left +right +1？ 直接left +right不就能取到0了吗？

是的，你可以写一下，但是这样必须初始化为right = n