当前位置：首页 > news >正文

关于二分查找的简单思考

news 2026/4/16 11:03:11

关于二分查找的简单思考

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

标准 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;