二分查找，什么时候用right=mid-1，什么时候用right=mid？

Question

我正在 leetcode https://leetcode.com/problems/leftmost-column-with-at-least-a-one/上解决这个问题，我想不出一个直观的答案。

为什么右（或高）指针有时设置为 mid - 1，为什么有时设置为 mid 是正确的？

我知道由于整数除法，我们必须始终设置 left = mid + 1。当只剩下两个元素时，我们需要设置 mid + 1 以避免无限循环。

但是什么情况下使用 right = mid - 1 和 right = mid 呢？

谢谢。

Answer 1

假设您正在对如下序列进行二分搜索

.....0, 0, 0, 0, 1, 1, 1, 1, ....

如果该值适用于，则您的决策函数fn将返回。truetrue1

现在考虑您的目标是找到 的最后一个位置0。在二分搜索的每个步骤中，我们将减少搜索空间，以便确定位置在范围内。如果fn返回，true您mid知道 的最后一个位置0将小于 mid （因为您希望 的最后一次出现0必须在 的第一次出现之前1）。所以，你会更新right=mid-1。如果fn返回 falseleft=mid.

现在考虑您的目标是找到 的第一次出现1。现在，如果fn返回，true您将更新，right=mid因为您知道 的第一次出现1将在此位置或其左侧。在这种情况下，如果fn返回false，则需要更新left=mid+1。