数据结构与算法 / 系统课时

写对二分边界与循环条件

写对二分边界与循环条件

二分搜索最容易错的往往不是思路,而是区间到底包不包含右端点。只要先确定搜索区间的语义,再让循环条件、舍弃方式和返回值保持一致,就能系统地避免死循环、越界以及漏掉最终答案。

学习目标

  • 区分左闭右闭 [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。

python
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])

预期输出:

text
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],确认代码返回的是题目要求的第一个或最后一个位置,而不是任意一个匹配位置。

真正稳定的二分模板不是背下来的几行代码,而是一个能持续回答的问题:**当前区间中哪些位置仍可能是答案?**只要每次更新后这句话仍成立,并且区间严格缩小,循环条件和最终返回值就很难写错。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

写对二分边界与循环条件

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

登录哪都通