数据结构与算法 / 技术文章
二分查找为什么总写错边界
二分查找最容易错的地方,不是“每次取中点”,而是你到底在搜索哪个区间、端点是否包含,以及循环结束后应该返回什么。掌握一套固定的区间定义,再让初始化、更新、终止条件全部服从这个定义,就能把常见的死循环、漏答案和越界问题一次理顺。
先把搜索区间说清楚
推荐先明确区间是闭区间 [left, right],还是半开区间 [left, right)。两种写法都正确,但初始化、循环条件和右边界更新必须成套出现,不能混用。
例如搜索有序数组中是否存在 target,采用闭区间时,含义是“答案仍可能出现在 left 到 right 的任意位置”,因此初始值通常是 left = 0、right = n - 1,循环条件对应 left <= right。
采用半开区间时,搜索范围表示 [left, right),右端点本身不参与搜索,因此初始值可以是 left = 0、right = n,循环条件改为 left < right。最常见的错误,就是初始化用了闭区间,却又写出半开区间的循环和更新规则。
中点不是重点,更新才决定会不会卡住
设当前中点为 mid。比较 nums[mid] 与目标值后,真正需要回答的是:中点已经排除后,剩余区间是什么。
对于闭区间 [left, right]:
nums[mid] < target:mid不可能是答案,左边界应变成mid + 1。nums[mid] > target:mid不可能是答案,右边界应变成mid - 1。nums[mid] == target:直接命中,或者根据题意继续收缩。
这里最关键的是 +1 和 -1。如果写成 left = mid 或 right = mid,当区间只剩两个元素时,mid 可能仍等于原来的边界,循环就无法缩小。
例如:
left = 0, right = 1
mid = 0此时如果左侧被排除,却只执行 left = mid,新的区间还是 0..1,下一轮仍可能得到相同的 mid,形成死循环。
循环条件必须和区间定义配套
可以把二分模板理解成一组互相绑定的规则:
| 区间定义 | 初始右边界 | 循环条件 | 排除 mid 后的左更新 | 排除 mid 后的右更新 |
|---|---|---|---|---|
[left, right] |
n - 1 |
left <= right |
mid + 1 |
mid - 1 |
[left, right) |
n |
left < right |
mid + 1 |
mid |
这张表针对查找任一等值元素。排除中点后,闭区间需要把右边界设为 mid - 1。半开区间设为 mid,因为右端点不包含,mid 同样已从下一轮可探查的下标中排除。比如 [0, 4) 中的中点为 2,右边界更新为 2 后只剩下标 0 和 1。
因此不要单独背“< 还是 <=”。更稳定的做法是先写一句区间不变量,例如“所有可能答案都位于 [left, right]”,然后逐条检查每次更新是否保持这个不变量。
查找一个值和查找第一个位置不是一回事
“找到 target 就返回”与“找到第一个大于等于 target 的位置”使用的停止方式不同。
如果目标是返回任意一个等于 target 的位置,可以在 nums[mid] == target 时立即返回。但如果题目要求“第一个等于 target 的位置”,命中后不能立刻结束,因为左侧仍可能存在更早的相同元素。
在按升序排列的数组中,nums[i] >= target 具有先不满足、再满足的单调结构。设边界 p 是第一个满足条件的下标,若不存在则令 p = n。以下算法保持 left <= p <= right。所有 i < left 的有效下标都已确认小于目标,所有 i >= right 的有效下标都已确认不小于目标。循环只探查 [left, right) 中的数组下标。当 nums[mid] >= target 时,设 right = mid。以后无需再探查它,但最终返回的边界仍可能正好等于这个 mid。
def lower_bound(nums, target):
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
def first_match(nums, target):
index = lower_bound(nums, target)
if index < len(nums) and nums[index] == target:
return index
return -1
assert lower_bound([], 2) == 0
assert lower_bound([2], 1) == 0
assert lower_bound([2], 3) == 1
assert lower_bound([1, 2, 2, 4], 2) == 1
assert lower_bound([1, 2, 2, 4], 3) == 3
assert lower_bound([1, 2, 2, 4], 5) == 4
assert first_match([1, 2, 2, 4], 2) == 1
assert first_match([1, 2, 2, 4], 3) == -1
print("边界测试通过")循环每次都严格缩短可探查区间,结束时两端相等,唯一边界就是返回值。数组为空时返回 0,目标大于所有元素时返回数组长度。标准库的插入位置契约见 Python bisect_left。
最容易漏掉的是空区间和答案不存在
边界题不能只拿“目标存在”验证。至少应该检查以下几类数据:
- 空数组。
- 只有一个元素。
- 目标在第一个位置。
- 目标在最后一个位置。
- 目标小于所有元素。
- 目标大于所有元素。
- 数组中存在多个相同元素。
这些用例分别覆盖初始化、第一次比较、左右端点更新、循环退出以及“没有答案”时的返回值。
例如使用 lower_bound 时,返回值等于 len(nums) 并不代表找到了元素,而是表示不存在满足条件的位置。因此如果题目要求判断 target 是否存在,还需要额外确认返回位置仍在数组范围内且值确实等于 target。
用不变量检查你的二分代码
面对一道新的二分题,不要先背模板,可以按下面顺序检查:
- 定义搜索区间,明确左右端点是否包含。
- 写出当前区间的含义,也就是区间不变量。
- 明确
mid被保留还是被排除。 - 根据上一条决定
left和right如何更新。 - 检查每次循环后区间是否严格缩小。
- 检查循环结束时,剩余边界分别代表什么。
- 用最小规模数据手算,特别是长度为
0、1、2的数组。
真正稳定的二分代码,核心不是某一份“万能模板”,而是让“区间定义、循环条件、边界更新、最终返回”四件事始终保持一致。只要这四处能够相互解释,二分查找里的边界错误就会从靠运气排错,变成可以机械验证的问题。