Python二分法查找end减一与不减一的区别:闭区间与开区间实现对比

江屿
江屿
发布时间:2026-11-16 | 3人浏览过
原创

深入对比Python二分查找中end减一与不减一的本质逻辑:闭区间与左闭右开区间的循环条件、指针收缩机制、死循环陷阱及模板选择指南。

在编写 Python 二分查找算法时,右指针 end 初始化到底是 len(nums) - 1 还是 len(nums),以及在收缩区间时到底写 end = mid - 1 还是 end = mid,常常困扰许多开发者。其实这并不是死记硬背的代码习惯,其根本区别在于你所选择的区间定义(循环不变量)。本文通过几何图解、代码对照与边界推导,彻底理清闭区间 [left, right] 与左闭右开区间 [left, right) 的设计逻辑。

一、核心结论:区间定义决定指针操作

二分查找的本质是在一个有序序列中,通过不断将候选范围折半来定位目标值。在整个查找过程中,维护一个始终包含目标候选值的有效区间,称为循环不变量(Loop Invariant)。

所谓的“减一”还是“不减一”,由两处代码协同决定:

  1. 初始化时:end = len(nums) - 1 代表候选范围是闭区间 [left, right];而 end = len(nums) 则代表左闭右开区间 [left, right)。
  2. 更新右边界时:当中间值大于目标值时,说明 mid 处的元素已被排除。如果是闭区间,下一轮的右边界必须不包含 mid,因此设为 right = mid - 1;如果是左闭右开区间,右边界本身在数学上就是不包含的开端,因此直接设为 right = mid 即可将 mid 排除在有效搜索范围之外。
Python二分法查找end减一与不减一的区别:闭区间与开区间实现对比
图1:闭区间与左闭右开区间的数学定义与初始指针位置对比

二、两套实现方案的代码与推导

为了看清内部机制,我们分别编写两套标准且符合 Python 规范的实现函数,并对照它们的每一处逻辑分支。

1. 方案一:闭区间写法(end 减一)

在闭区间模型中,我们认为区间 [left, right] 内的所有索引都是合法且待核验的候选。

def binary_search_closed(nums: list[int], target: int) -> int:
    left = 0
    right = len(nums) - 1  # 初始区间 [left, right] 包含最后一个有效元素

    while left <= right:   # 当 left == right 时,[left, right] 仍包含一个元素,需要继续判断
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1  # target 在右半部分,排除当前 mid
        else:
            right = mid - 1 # target 在左半部分,排除当前 mid,右边界必须减一

    return -1  # 未找到目标值
推导要点:
  • 为什么 while left <= right? 当搜索缩减到只剩一个元素时,left == right。例如在 [3, 3] 中,索引 3 仍未与 target 进行比对,必须进入循环执行一次检查。
  • 为什么 right = mid - 1? 当 nums[mid] > target 时,已知 nums[mid] 绝不可能是目标值。既然区间是两端闭合的,如果不把 right 移到 mid - 1,下一次搜索范围 [left, right] 就会依然包含 mid,这破坏了“待查区间”的不变量定义。

2. 方案二:左闭右开区间写法(end 不减一)

在左闭右开模型中,right 仅作为搜索边界的开端标记,表示“搜索范围包含 left,但直到 right 前一位为止(不包含 right)”。这与 Python 原生的 range(0, n) 和切片 nums[0:n] 逻辑完全一致。

def binary_search_half_open(nums: list[int], target: int) -> int:
    left = 0
    right = len(nums)      # 初始区间 [left, right),不减一,末位元素索引为 right - 1

    while left < right:    # 当 left == right 时,[left, right) 为空集,无元素可查,循环退出
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1  # target 在右半部分,排除当前 mid
        else:
            right = mid     # target 在左半部分,排除当前 mid;因右边界开区间,设为 mid 即可排除

    return -1  # 未找到目标值
推导要点:
  • 为什么 while left < right? 如果 left == right,例如 [4, 4),在数学定义上这是一个空区间,没有任何元素可以被访问。此时循环必须终止。
  • 为什么 right = mid 而不减一? 当 nums[mid] > target 时,我们需要排除 mid。因为右边界本身不包含在候选范围内,将 right 设置为 mid 后,新的搜索区间变成 [left, mid),它恰好包含 left 到 mid - 1,完美排除了 mid。
Python二分法查找end减一与不减一的区别:闭区间与开区间实现对比
图2:闭区间与左闭右开区间在同一数组中的推导步进对比

三、混用区间导致的典型错误与死循环根源

许多开发者在写二分查找时出现 Bug 或死循环,90% 以上的原因都是因为混淆了区间模型,把闭区间的循环条件和开区间的边界更新拼凑在了一起。

1. 错误案例一:闭区间条件下写了 right = mid(死循环)

如果在闭区间 while left <= right 下错误地把右侧收缩写成 right = mid,在查找不存在的数或数组仅剩两个元素时,极易陷入死循环。

例如当 nums = [2, 8],要找 target = 1:

  • 初始状态:left = 0, right = 1。
  • 第一轮:mid = 0,nums[0] = 2 > 1,执行 right = mid = 0。
  • 第二轮:left = 0, right = 0,条件 0 <= 0 成立进入循环。计算 mid = 0,由于 nums[0] = 2 > 1,再次执行 right = mid = 0。
  • 指针永远停在 left = 0, right = 0,程序进入无限循环。

2. 错误案例二:开区间条件下写了 while left <= right(数组越界)

如果采用了 right = len(nums) 的开区间初始值,却在循环条件中写成 while left <= right:

  • 当目标值比数组中所有元素都大时,left 会一路右移直到 left = len(nums)。
  • 因为条件是 left <= right,此时 left == right == len(nums) 依然满足循环条件!
  • 进入循环后计算 mid = len(nums),接着执行 nums[mid],立即引发 IndexError: list index out of range 异常崩溃。
Python二分法查找end减一与不减一的区别:闭区间与开区间实现对比
图3:混用区间破坏循环不变量导致的死循环与数组越界场景剖析

四、两套区间的对比与选型指南

两种方式在时间复杂度上完全一致,均为 \(O(\log n)\),在空间复杂度上也均为 \(O(1)\)。实际编码中应当如何选择?

对比维度 闭区间 [left, right] 左闭右开区间 [left, right)
初始 end 设置 len(nums) - 1(减一,指向末位元素) len(nums)(不减一,指向虚拟右界)
循环继续条件 while left <= right while left < right
向左收缩(排除mid) right = mid - 1 right = mid
向右收缩(排除mid) left = mid + 1 left = mid + 1
单元素区间表示 [i, i](有效,含1个元素) [i, i+1)(有效,含1个元素)
空区间判定 left > right 时为空 left == right 时为空
Python生态契合度 符合数学直觉,边界左右对称 完全契合 range() 与切片语法,契合标准库 bisect
Python二分法查找end减一与不减一的区别:闭区间与开区间实现对比
图4:二分查找核心要素与指针操作决策矩阵速查表

五、编写二分法的实践建议

  1. 选定一种形成肌肉记忆:在面试或日常算法题中,建议初学者固定使用闭区间模型(len(nums) - 1 与 left <= right),因为它的左右边界更新形式都是对称的(left = mid + 1 与 right = mid - 1),最符合数学直觉,不容易遗漏减号。
  2. 处理切片和子区间时用开区间:如果你经常需要将二分找到的索引与 Python 的 range()、列表切片 nums[:idx] 或者标准库 bisect.bisect_left() 配合,左闭右开区间能让你的返回值直接作为切片右界,无需任何 +1 或 -1 修正。
  3. 牢记循环不变量:动手写代码前,先问自己一句:“我的 right 指向的那个位置,到底还需不需要被检查?”如果是,就减一用闭区间;如果只是个哨兵边界,就不减一用开区间。始终保持初始状态、循环条件与收缩逻辑的一致性,就能彻底告别死循环与越界 Bug。
相关专题:

本站声明

本文内容仅供参考,不代表本站观点。转载或引用请注明出处。如发现内容问题,请通过联系我们页面反馈。

Python 相关产品和应用

全部下载

专题列表