数据结构与算法 / 技术文章

二分查找为什么总写错边界

二分查找最容易错的地方,不是“每次取中点”,而是你到底在搜索哪个区间、端点是否包含,以及循环结束后应该返回什么。掌握一套固定的区间定义,再让初始化、更新、终止条件全部服从这个定义,就能把常见的死循环、漏答案和越界问题一次理顺。

先把搜索区间说清楚

推荐先明确区间是闭区间 [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 可能仍等于原来的边界,循环就无法缩小。

例如:

text
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。

python
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。

用不变量检查你的二分代码

面对一道新的二分题,不要先背模板,可以按下面顺序检查:

  1. 定义搜索区间,明确左右端点是否包含。
  2. 写出当前区间的含义,也就是区间不变量。
  3. 明确 mid 被保留还是被排除。
  4. 根据上一条决定 left 和 right 如何更新。
  5. 检查每次循环后区间是否严格缩小。
  6. 检查循环结束时,剩余边界分别代表什么。
  7. 用最小规模数据手算,特别是长度为 0、1、2 的数组。

真正稳定的二分代码,核心不是某一份“万能模板”,而是让“区间定义、循环条件、边界更新、最终返回”四件事始终保持一致。只要这四处能够相互解释,二分查找里的边界错误就会从靠运气排错,变成可以机械验证的问题。

目录与阅读设置

记录一个想法

二分查找为什么总写错边界

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通