Python手写二分查找为何容易出错？边界条件解析

一、一个直观场景：为什么简单逻辑会瞬间卡死？

假设我们要在升序列表 nums = [2, 5] 中查找目标值 5。许多初学者凭借直觉写出如下代码：

def bad_binary_search(nums, target):
    left = 0
    right = len(nums) - 1  # 初始区间：[0, 1]
    while left < right:
        mid = (left + right) // 2  # mid = 0
        if nums[mid] < target:
            left = mid  # 这里写成了 left = mid，期望缩小左边界
        else:
            right = mid
    return left if nums[left] == target else -1

运行这段代码，程序并不会返回正确索引 1，而是直接陷入永久死循环。原因在于：当搜索范围只剩 [2, 5] 两个元素时，mid = (0 + 1) // 2 结果为 0。由于 nums[0] (2) < 5，分支执行 left = mid，赋值后 left 依然是 0。搜索区间没有任何缩小，下一轮循环依然计算出 mid = 0，程序因此永远无法退出。

计算机科学家高德纳（Donald Knuth）曾指出：“虽然二分查找的基本思想相对简单，但其细节却出奇地微妙。” 手写二分查找容易出错的根本根源，就在于区间定义不统一以及由此引发的边界收缩逻辑失真。

二、核心根源：区间不变量（Loop Invariant）的自洽性

所谓区间不变量，指的是在循环开始前、循环执行过程中以及循环退出后，我们对变量 left 和 right 所构成的搜索区间的数学定义必须自始至终保持一致。二分查找的代码中存在三大核心要素：

1. 右指针初始值（len(nums) - 1 还是 len(nums)）
2. 循环继续的判定条件（left <= right 还是 left < right）
3. 左右边界的更新公式（right = mid - 1 还是 right = mid）

这三者是一套严密的数学契约，不能随意组合。一旦混用不同模型的规则，就会直接破坏不变量，导致漏检元素或陷入死循环。

1. 模式一：双闭区间 [left, right] 的实现

在双闭区间模型中，我们认定的有效搜索范围是 [left, right]，即下标为 left 和 right 的元素都有可能是目标值。标准实现如下：

def binary_search_closed(nums, target):
    left = 0
    right = len(nums) - 1  # 初始区间覆盖所有合法索引 [0, n-1]

    while left <= right:  # 当 left == right 时，区间内依然包含 1 个元素，需要检查
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1  # mid 已经被检查过且不符合，排除 mid，区间变为 [mid + 1, right]
        else:
            right = mid - 1  # 排除 mid，区间变为 [left, mid - 1]

    return -1  # 循环结束时 left > right，区间为空，说明目标值不存在

2. 模式二：左闭右开区间 [left, right) 的实现

在左闭右开区间模型中，right 充当的是“边界哨兵”，当前搜索范围不包含 right 对应的位置：

def binary_search_half_open(nums, target):
    left = 0
    right = len(nums)  # 注意：初始 right 取数组长度，因为区间是右开的

    while left < right:  # 当 left == right 时，[left, left) 是空区间，无元素可查
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1  # 下一轮有效搜索区间为 [mid + 1, right)
        else:
            right = mid  # 下一轮有效搜索区间为 [left, mid)，由于是右开，自动排除了 mid

    return -1

三、三大高频致命边界与死循环陷阱

1. 陷阱一：循环条件与区间开闭不匹配

很多开发者在闭区间写法中误将循环条件写成 while left < right。这种写法会导致当区间收缩到只剩下 1 个元素（即 left == right）时，循环提前退出。如果目标值恰好就是这最后一个元素，算法将直接漏检，错误返回 -1。

2. 陷阱二：区间收缩时的下取整死锁

在 Python 中，整除运算符 // 默认向下取整（如 1 // 2 == 0）。当搜索区间只剩下两个相邻元素时（即 right == left + 1），计算得到的 mid 必然等于 left。此时：

• 如果代码中错误写成 left = mid，left 的值将完全没有变化，区间大小依然维持为 2，程序陷入死循环。
• 如果写成 left = mid + 1，left 将增加 1 与 right 重合，搜索范围成功减半，死循环得以避免。

3. 陷阱三：中点溢出与 Python 负索引陷阱

在 C/C++ 或 Java 中，(left + right) // 2 可能会因为两数相加超出整型最大值（2³¹ - 1）而发生溢出错误，因此通常写作 left + (right - left) // 2。虽然 Python 的整数类型（int）支持任意精度的动态大数、不会发生整型溢出，但使用 left + (right - left) // 2 仍具有显著优点：它能够清晰传达“在基准点 left 上累加半长偏移量”的语义，具有更好的工程规范性。

此外，Python 有一个特有的隐蔽陷阱：负索引支持。如果指针 right 在收缩过程中意外递减至 -1，在 C/C++ 中会立即触发数组越界崩溃（SIGSEGV），便于迅速排查；但在 Python 中，nums[-1] 不会报错，而是会默默读取列表最后一个元素。这种静默错误会导致算法逻辑在暗中发生漂移，极大增加排查难度。因此，保持指针严格在非负范围内收缩至关重要。

四、进阶场景：有序包含重复元素时的左右边界查找

当有序列表中存在多个相同的元素时，普通二分查找只能随机返回其中任意一个的索引。如果要获取目标值首次出现的下标（左边界 / lower_bound）或最后出现的下标（右边界 / upper_bound），就必须在 nums[mid] == target 时做出特殊处理。

1. 寻找最左侧边界（Lower Bound）

当 nums[mid] == target 时，不要立即返回 mid，因为左边可能还有相同的目标值。此时应收缩右边界，锁定包含 mid 及其左侧的区间：

def binary_search_left_bound(nums, target):
    left = 0
    right = len(nums)  # 采用左闭右开区间 [left, right)

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] >= target:
            right = mid  # 即使等于 target，也继续向左挤压右界
        else:
            left = mid + 1

    # 循环结束时 left == right，需验证越界和命中状态
    if left >= len(nums) or nums[left] != target:
        return -1
    return left

2. 寻找最右侧边界（Upper Bound）

同理，当寻找最右侧边界时，遇到 nums[mid] == target 应当增加 left，继续向右侧探测：

def binary_search_right_bound(nums, target):
    left = 0
    right = len(nums)

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1  # 即使等于 target，也继续向右挤压左界
        else:
            right = mid

    # 循环结束时，left 指向的是严格大于 target 的第一个元素，因此对应目标索引应为 left - 1
    if left - 1 < 0 or nums[left - 1] != target:
        return -1
    return left - 1

五、总结：手写二分查找的自查清单

在算法面试或实际业务编码中，只要严格对照以下四项自查标准，就能彻底消除二分查找的边界 Bug：

1. 区间选型确认：明确选择使用“双闭区间”还是“左闭右开区间”。通常推荐首选双闭区间（right = len(nums) - 1），逻辑最符合直觉。
2. 循环条件配对：若选双闭，写 while left <= right；若选左闭右开，写 while left < right。绝不能混用。
3. 收缩严格排他：排除目标不在的区间时，必须对 mid 做 +1 或 -1 偏移，绝不可在没有调整向上取整机制时直接写 left = mid，避免陷入死循环。
4. 特值极端验证：手写完成后，迅速在脑海中使用 nums = []（空列表）、nums = [1]（单元素命中与未命中）、nums = [1, 2]（两元素分别命中首尾）进行干跑（Dry Run）验证。