二分查找中如何确定边界？

Question

我知道二分搜索是如何工作的，但当我需要实现二分搜索时，我总是会犯一些小错误。

以下代码是leetcode 287查找重复数字的解决方案

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low = 1, high = nums.size() - 1;
        while (low < high) {
            int mid = low + (high - low) * 0.5;
            int cnt = 0;
            for (auto a : nums) {
                if (a <= mid) ++cnt;
            }
            if (cnt <= mid) low = mid + 1;
            else high = mid;
        }
        return low;
    }
};

有几个地方让我很困惑：

1. while循环的条件low<high or low<=high

2. a<=mid or a<mid（具体针对本例）

3.cnt<= mid or cnt<mid

4.low=mid+1 or low=mid

5.high=mid or high=mid-1

6.我要返回哪个值？

有没有一个好方法来记住或理解要使用哪些正确的组合？

Answer 1

在编写二分搜索时，需要考虑一些事情。第一个是您正在搜索的区间范围，具体来说，您如何定义它。

例如，它可以包含 和low,high意思是[low, high]，但也可以不包含high, [low, high)。您选择的其中哪一个将改变您算法的其余部分。

明显的含义是初始值。一般来说，high如果它是独占的，则应该是数组的长度，如果它是包含的，则应该是数组的长度，但根据您要解决的问题，它可能完全不同。

对于 while 循环，您希望它在搜索间隔为空时终止，这意味着没有更多候选者需要检查。如果您使用间隔，那么当严格大于（例如，包含 5，但不包含任何内容）时，[low, high]这将为空，因此 while 循环将检查相反的。但是，如果使用间隔，则当等于时此间隔为空，因此 while 循环需要检查 for 。lowhigh[5,5][6,5]low <= high[low, high)lowhighlow < high

在 while 循环中，检查后mid，您希望将其从间隔中删除，这样就不会再次检查它。如果high包含在内，则必须使用小于 1 的值mid作为新值high，以便将其从间隔中排除。但如果high是排他的，那么设置high等于mid就足以排除它。

至于何时更新lowvs high，这取决于您要搜索的内容。除了基本的二分搜索（您只想知道集合中是否存在某些内容）之外，您还必须考虑当您尽可能接近时该怎么做。

例如，在 C++ 中，更有用的版本binary_search称为lower_bound和upper_bound。如果容器中不存在要搜索的值，则它们都返回相同的位置，即第一个大于搜索值的位置。这很方便，因为如果您想保持容器排序，则应在此处插入该值。但是，如果该值在容器中（可能多次），则将lower_bound返回该值的第一次出现，而upper_bound仍将返回大于该值的第一个位置（或者换句话说，右边界到该值的位置） ）。

要获得这些不同的行为，您可以在等于搜索值时更新low或high绑定。mid如果你想要下限，那么你想继续搜索搜索范围的下半部分，所以你把它降下来high。如果你想要上限，那么你就提出low。在您的示例中，它会显示low何时cnt == mid，因此它将找到一个上限。

至于返回什么，这取决于您的搜索间隔和您要查找的内容。在您的示例中， while 循环正在检查(low < high)，因此当它中断时low和high将相等，并且您使用哪个并不重要，但即使如此，您可能想要返回left - 1orleft + 1取决于问题。如果 while 循环是(low <= high)then 当它 Break 时low == high + 1，那么这将取决于您要寻找的内容。当有疑问时，你总是可以通过一个例子来思考。

因此，为了充分利用这一切，这是您提到的解决方案的一个版本，但使用 [low, high] 间隔而不是 [low, high)：

class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            int low = 1, high = nums.size() - 2;
            while (low <= high) {
                int mid = low + (high - low) * 0.5;
                int cnt = 0;
                for (auto a : nums) {
                    if (a <= mid) ++cnt;
                }
                if (cnt <= mid) low = mid + 1;
                else high = mid - 1;
            }
            return low;
        }
    };

PS：我没有提到间隔的原因(low, high]是(low, high)因为它与计算指数的数学混乱mid。mid因为 int math 会向下舍入，所以您可能会遇到再次搜索的情况。例如，如果low是 7 且high是 9，则将low + (high - low) * 0.5为 8。将 low 更新为 8 后（因为它是独占的，因此您不会添加 1），low + (high - low) * 0.5仍将是 8 并且循环永远不会终止。您可以通过在除以 2 的部分上加 1 来解决这个问题，但通常使用包含low在内的区间会更干净。

Answer 2

您可以使用 leetcode 的二分搜索指南作为参考。https://leetcode.com/explore/learn/card/binary-search