算法刷题系列（二十二）：二分查找——在单调条件中定位边界
算法刷题系列（二十二）：二分查找——在单调条件中定位边界
二分查找不只是“在有序数组里找一个数”。更一般的用法是：当某个条件沿着搜索范围只从假变真、或只从真变假时，利用一次判断排除一半候选位置。本文先用有序数组寻找第一个不小于目标值的位置，再比较闭区间和半开区间两种写法。
前面的双指针和滑动窗口依赖边界向一个方向移动；二分查找则要求判断结果具有单调性。若题目只有“看起来大致有序”，却不能证明单调条件，就不能直接二分。
一、把查找改写成边界问题
数组 [-4, 1, 1, 1, 8] 中查找 1，返回任意一个 1 并不总够用。若问题要求“第一个大于等于 1 的位置”，可把每个位置的判断写成：
1
2
值 < 1：假 假 假
值 >= 1：真 真
目标就是第一个真值。若数组中不存在满足条件的元素，答案定义为数组长度 n，正好表示插入位置。
二、闭区间与半开区间的不变式
闭区间 [left, right]
初始搜索范围覆盖全部元素。循环条件是 left <= right，中点不满足条件时分别令 left = mid + 1 或 right = mid - 1。区间缩小到空后，left 落在第一个可能满足条件的位置。
半开区间 [left, right)
右端点不属于搜索范围，初始值是 [0, n)。循环条件为 left < right。若 mid 已满足“值大于等于目标”，将右边界缩至 mid；否则把左边界移到 mid + 1。循环结束时 left == right，就是边界位置。
两种约定都正确，关键是始终坚持同一套区间定义。半开区间天然允许空数组，也无需计算 n - 1。
三、手推一个例子
对 [-4, 1, 1, 1, 8] 查找 1，半开区间从 [0, 5) 开始。中点 2 的值为 1，边界可能在 2 或更左，于是变为 [0, 2)；接着中点 1 也是 1，缩到 [0, 1)；最后中点 0 的值小于 1，左边界变成 1。返回索引 1。
四、Java：半开区间 lower bound
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Main {
static int lowerBound(int[] values, int target) {
int left = 0;
int right = values.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (values[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public static void main(String[] args) {
int[] values = {-4, 1, 1, 1, 8};
assert lowerBound(values, 1) == 1;
assert lowerBound(values, 2) == 4;
assert lowerBound(values, -9) == 0;
assert lowerBound(new int[0], 3) == 0;
}
}
五、Python：相同不变式
1
2
3
4
5
6
7
8
9
10
11
12
13
def lower_bound(values: list[int], target: int) -> int:
left, right = 0, len(values)
while left < right:
mid = left + (right - left) // 2
if values[mid] >= target:
right = mid
else:
left = mid + 1
return left
assert lower_bound([-4, 1, 1, 1, 8], 1) == 1
assert lower_bound([-4, 1, 1, 1, 8], 2) == 4
assert lower_bound([], 3) == 0
六、正确性、复杂度与边界
循环每一步都保留“答案不在已排除区域”的可能性：中点满足条件时，中点本身可能就是第一个真值，所以不能排除它；中点不满足时，它及左侧都不可能满足，可以安全跳到 mid + 1。区间长度每次至少减半，最终只剩唯一插入边界。
- 时间复杂度：
O(log n)；空间复杂度：O(1)。 - 空数组返回 0；目标小于所有元素返回 0；目标大于所有元素返回
n；重复值由定义决定返回最左侧位置。 - 求第一个
> target的位置时，应将条件改为values[mid] > target；这就是 upper bound。
常见错误是闭区间循环里忘记排除 mid，导致区间不缩小；或在半开区间里把 right 初始化成 n - 1，遗漏最后一个候选。中点用 left + (right - left) / 2，比 (left + right) / 2 更能避免整数加法溢出。
小结与衔接
二分查找的核心是单调谓词与明确的不变式，而不只是数组排序。掌握边界后，可以把它用于答案空间上的“最小可行值”或“最大可行值”搜索。下一篇的三分搜索也会缩小候选区间，但它依赖的是单峰形状，不是真假谓词的单调边界。