algorithm - 二分查找，什么时候用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，vs right = mid？

谢谢。

标签： algorithmsortingpointersbinary-search

Answer 1

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

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

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

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

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