数据结构与算法 / 系统课时
写对二分边界与循环条件
写对二分边界与循环条件
二分搜索最容易错的往往不是思路,而是区间到底包不包含右端点。只要先确定搜索区间的语义,再让循环条件、舍弃方式和返回值保持一致,就能系统地避免死循环、越界以及漏掉最终答案。
学习目标
- 区分左闭右闭
[left, right]与左闭右开[left, right)两种区间语义 - 为两种区间选择匹配的循环条件和边界更新方式
- 根据区间是否真正缩小定位常见的死循环与漏解错误
先固定区间语义
写二分前先用一句话定义变量含义。例如:left 和 right 当前表示哪些下标仍可能包含答案?只要这句话在整个循环里始终成立,边界代码就不需要靠记忆拼凑。
两种常用写法都正确,但不能混搭:
| 写法 | 搜索区间 | 初始右边界 | 循环条件 | 区间为空时 |
|---|---|---|---|---|
| 左闭右闭 | [left, right] |
n - 1 |
left <= right |
left > right |
| 左闭右开 | [left, right) |
n |
left < right |
left == right |
左闭右闭中,right 指向一个仍待检查的元素;左闭右开中,right 本身不属于搜索区间。因此一个从 n - 1 开始,一个从 n 开始,这是两套代码最根本的区别。
用同一个目标比较两套写法
下面两种实现都寻找有序数组中第一个大于等于 target 的位置,也就是常见的 lower_bound。测试数组为 [1, 3, 3, 5, 8],目标值为 4,正确位置应是下标 3,对应元素 5。
from typing import List
def lower_bound_closed(nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
answer = len(nums)
# 闭区间只要 left <= right,就仍有候选元素需要检查。
while left <= right:
mid = left + (right - left) // 2
if nums[mid] >= target:
answer = mid
right = mid - 1
else:
left = mid + 1
return answer
def lower_bound_half_open(nums: List[int], target: int) -> int:
left, right = 0, len(nums)
# 半开区间在 left == right 时已经收缩到唯一插入位置。
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
return left
if __name__ == "__main__":
nums = [1, 3, 3, 5, 8]
for search in (lower_bound_closed, lower_bound_half_open):
index = search(nums, 4)
print(index, nums[index])预期输出:
3 5
3 5闭区间版本检查完 mid 后,会把已经确定不需要继续搜索的位置一起删除,因此使用 right = mid - 1 或 left = mid + 1。半开区间版本中,若 nums[mid] >= target,mid 自己仍可能是第一个满足条件的位置,所以右边界更新为 right = mid。
用“是否严格缩小”排查死循环
二分循环每执行一次,候选区间都必须严格变小。遇到超时或死循环时,不要先改循环条件,而应检查某个分支是否可能让 left、right 完全不变。
例如采用 mid = (left + right) // 2 时,当区间只剩相邻两个位置,可能出现 mid == left。如果某个分支仍执行 left = mid,左边界就没有移动;下一轮会计算出完全相同的 mid,循环永远无法结束。
因此,对于“已经确认 mid 不可能是答案”的分支,应跨过它,使用 left = mid + 1 或 right = mid - 1。只有当 mid 仍可能是最终答案时,才应该用 right = mid 之类的更新把它保留下来。
返回值必须和循环结束状态对应
闭区间写法结束时通常有 left > right。如果是在寻找第一个满足条件的位置,可以额外维护 answer,也可以根据具体不变量返回 left;但必须提前证明结束后该变量代表什么。
半开区间模板通常更适合寻找边界。循环结束时 left == right,整个候选区间已经收缩到一个插入位置,因此直接返回 left 很自然。即使目标值大于数组所有元素,它也会返回 n,这与“插入到数组末尾”的定义一致。
不要因为某道题答案碰巧正确,就随意把 left <= right 改成 left < right,或者把 right = mid - 1 改成 right = mid。二分的四个部分——区间定义、循环条件、边界更新、返回值——必须作为一套整体设计。
写完二分后的边界检查
提交前至少手动验证空数组或最小规模、答案在最左端、答案在最右端以及目标不存在这几类情况。对于寻找边界的题,还应加入大量重复元素,例如 [2, 2, 2, 2],确认代码返回的是题目要求的第一个或最后一个位置,而不是任意一个匹配位置。
真正稳定的二分模板不是背下来的几行代码,而是一个能持续回答的问题:**当前区间中哪些位置仍可能是答案?**只要每次更新后这句话仍成立,并且区间严格缩小,循环条件和最终返回值就很难写错。