关于二分查找的简单思考

二分查找是排列组合？总是写出死循环？笔者给出自认为的正确的二分查找思考方式。

标准 Binary-Search 的两种形式

参考 C++ <algorithm> 库，我们发现有两种二分查找的常用算法^[1]：

• lower_bound(ranges::lower_bound): 寻找到范围内第一个不小于给定值的值。
• upper_bound(ranges::upper_bound): 寻找到范围内第一个大于给定值的值。

这样我们就明确了我们的目标：返回一个区间，这个区间有且仅有一个数，满足我们所给定的上述条件。我们将我们的区间定义为 \([l, r]\), 那么目标就是返回其中的一个指针，我们一般将会返回 \(l\)。

寻找循环不变量

接下来，对于我们的区间，我们需要寻找一个称为循环不变量的东西。这个东西告诉我们我们在进行二分查找时，所选定的范围应该满足什么条件，这个条件将会贯穿我们整个二分查找的所有环节，直到我们的区间为空（无法继续二分查找）。

我们可以利用逆向思维，在区间为空的情况下，从结果导出我们的循环不变量。

• 针对lower_bound: 我们的left最终需要指向第一个不小于目标值的值。区间为空的时候，right == left - 1。因此我们需要
  nums[l-1] < target && nums[r+1] >= target.
• 针对upper_bound: 我们的left最终需要指向第一个大于目标值的值。区间为空的时候，right == left - 1。因此我们需要：
  nums[l-1] <= target && nums[r+1] > target.

这样就是我们在更新区间时所必须要遵守的规则。在区间更新后，所有的新区间[l',r']都应该对应满足以上的条件。

更新区间

对于区间的描述，我们将具有四种区间的描述方法：
[l, r], [l, r), (l, r], (l, r)。四种描述方法都可以作为我们进行二分查找的方式。下面我们具体进行分析。^[2]

lower_bound 区间更新

在寻找到中间量mid后，我们将会使用 nums[mid] 和 target 进行比较。很明显，比较结果具有以下三种情况。我们再次重申我们的循环不变量：

nums[l-1] < target && nums[r+1] >= target

区间修改方式：lower_bound

• nums[mid] < target. 这时我们需要有：
  l' = mid + 1, r' = r。这样保证了我们
  nums[l'-1] = nums[mid] < target, nums[r + 1] >= target,
  虽然r+1可能已经越界，但是单调非递减数组的情况下这是成立的。
• nums[mid] == target. 这时我们需要有：
  l' = l, r' = mid - 1。这样保证了我们
  nums[l'-1] = nums[mid] < target, nums[r + 1] >= target,
  虽然l-1可能已经越界，但是单调非递减数组的情况下这是成立的。
• nums[mid] > target. 这时我们需要有：
  l' = l, r' = mid - 1。这样保证了我们
  nums[l'-1] = nums[mid] < target, nums[r + 1] >= target,
  虽然l-1可能已经越界，但是单调非递减数组的情况下这是成立的。

区间终点: left > right

我们的区间终点就是空集。因此我们需要在left > right的情况下终止。此时根据循环不变量，我们的nums[l-1] < target && nums[r+1] >= target。在上述情况下，如果target大于所有的数，最终l将会在指向nums.length()时终止(r不会越界)。在target小于所有数的时候，最终r会指向-1(l不会越界)。因此结果是符合预期的。

这样我们就有：

int left = 0, right = nums.size() - 1;
while (left <= right) {
    int mid = (left + right) / 2;
    if (nums[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
return left;

那么针对其他的区间，我们就可以分析：

• [l, r)，则实际上是 [l, r - 1]。我们就有：
  l = 0, r = nums.size() -> 起始条件。
  left <= right - 1 -> while 条件
  int mid = (left + right - 1) / 2 -> 中点。
  l = mid + 1, r - 1 = mid - 1 -> l不变， r = mid.
  返回l.
• (l, r]，则实际上是 [l + 1, r]。我们有：
  l = -1, r = nums.size() - 1 -> 起始条件。
  left + 1 <= right -> while 条件
  int mid = (left + 1 + right) / 2 -> 中点。
  l + 1 = mid + 1, r = mid - 1 -> r不变， l = mid.
  返回l + 1.
• (l, r)，则实际上是 [l+1, r-1]。我们留给读者作为练习 我最讨厌这样的作者了，还是认真写吧。
  l = -1, r = nums.size() -> 起始条件。
  left + 1 <= right - 1 -> while 条件
  int mid = (left + 1 + right - 1) / 2 -> 中点。
  l + 1 = mid + 1, r - 1 = mid - 1 -> r = mid， l = mid.

这样我们直接给出代码。

// [l, r)
int left = 0, right = nums.size();
while (left <= right - 1) {
    int mid = (left + right - 1) / 2;
    if (nums[mid] < target) {
        left = mid + 1;
    } else {
        right = mid;
    }
}
return left;

// (l, r]
int left = -1, right = nums.size() - 1;
while (left + 1 <= right) {
    int mid = (left + right + 1) / 2;
    if (nums[mid] < target) {
        left = mid;
    } else {
        right = mid - 1;
    }
}
return left + 1;

// (l, r)
int left = -1, right = nums.size();
while (left + 1 <= right - 1) {
    int mid = (left + right) / 2;
    if (nums[mid] < target) {
        left = mid;
    } else {
        right = mid;
    }
}
return left + 1;

这样我们的lower_bound就可以在四种范式下写出。再也不用担心写出死循环了！ 我们发现，我们只需要记住：循环不变量+根据循环不变量变换区间的方法即可。

Upper_bound 区间更新

在寻找到中间量mid后，我们将会使用 nums[mid] 和 target 进行比较。很明显，比较结果具有以下三种情况。我们再次重申我们的循环不变量：

nums[l-1] <= target && nums[r+1] > target

我们就只写出[l,r]的所有情况，剩下的情况按照上述方式推导即可。

• nums[mid] < target. 这时我们需要有：
  l' = mid + 1, r' = r。这样保证了我们
  nums[l'-1] = nums[mid] <= target, nums[r + 1] > target,
  虽然r+1可能已经越界，但是单调非递减数组的情况下这是成立的。
• nums[mid] == target. 这时我们需要有：
  l' = mid + 1, r' = r。这样保证了我们
  nums[l'-1] = nums[mid] <= target, nums[r + 1] > target,
  虽然r+1可能已经越界，但是单调非递减数组的情况下这是成立的。
• nums[mid] > target. 这时我们需要有：
  l' = l, r' = mid - 1。这样保证了我们
  nums[l'-1] = nums[mid] <= target, nums[r + 1] > target,
  虽然l-1可能已经越界，但是单调非递减数组的情况下这是成立的。

这样我们有：

int left = 0, right = nums.size() - 1;
while (left <= right) {
    int mid = (left + right) / 2;
    if (nums[mid] <= target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
return left;

非标准二分查找

非标准的二分查找采用“区间判别法”。
例如，二分查找可以泛化成：寻找第一个/最后一个符合条件的。我们记为 check(i)。

那么，我们有如下的示例：

如果后者我们继续沿用左闭右开区间呢？稍微改一下循环不变量就好了。