二分查找边界条件详解：从手写实现到Python bisect实战

二分查找不是一个“会不会背模板”的问题而是一个“边界条件写不写得对”的问题。很多初学者第一次写二分查找都能写出大概逻辑但一运行就出现死循环、漏掉元素、下标越界或者面对“查找第一个等于目标值的位置”“查找最后一个小于目标值的位置”这类变体时直接懵掉。这篇文章不绕弯子直接讲清楚二分查找的原理、两种最常见的区间写法、各种变体怎么写以及 Python 内置的bisect模块在工程里怎么用。文中所有代码都基于 Python 3不需要额外安装任何第三方库复制到本地就能运行。内容覆盖基础实现、边界写法、性能对比、LeetCode 经典例题、常见报错排查读完可以直接把模板沉淀到自己的代码库里。1. 二分查找核心能力速览先把二分查找的核心信息拉出来方便快速判断它适合解决什么问题。能力项说明算法类型基于有序数组的搜索算法时间复杂度O(log n)数据量翻倍时比较次数只增加一次空间复杂度迭代法 O(1)递归法 O(log n)前置条件数组/列表必须有序升序或降序输入形式Python list、array 等支持随机访问的序列核心操作每次取中间元素与目标值比较排除一半区间主要功能查找目标值、查找左边界、查找右边界、插入位置定位内置库支持bisect模块生产环境推荐直接使用适合场景静态有序数据、搜索定位、区间查询、算法竞赛、面试题不适合场景无序数据、频繁插入删除的链表、数据量极小且只需一次搜索二分查找的价值不在于“在一个数组里找一个数”这个场景有多复杂而在于它是很多高级算法的基础。比如旋转排序数组的最小值、寻找峰值、求平方根、有序矩阵搜索底层都是二分思想。理解二分查找的边界处理后面这些题都会顺利很多。2. 二分查找的适用场景与使用边界2.1 什么时候应该用二分查找二分查找解决的核心问题只有一个在有序序列中快速定位目标或目标区间。具体来说以下几类场景非常典型。第一静态有序数据的高频搜索。比如一个按 ID 升序排列的用户列表需要频繁判断某个 ID 是否存在一个按时间排序的日志数组需要快速定位某条时间戳的位置。数据只构建一次但查询很多次这时二分查找比逐一遍历划算得多。第二需要“找到插入位置”的场景。比如维护一个有序列表每次插入新元素都要保持顺序可以直接用二分查找确定索引位置再执行插入操作。bisect模块正是为这种场景设计的。第三算法题中二分答案的套路。很多最优化问题的思路是枚举一个答案判断它是否可行然后在这个答案的取值范围内二分。典型例子包括“在 D 天内送达包裹的能力”“分割数组的最大值”这类题目。这种场景不是直接搜数组元素而是把二分思想套在答案值域上。2.2 什么时候不应该用二分查找不是所有“找元素”的问题都适合二分查找。如果数据本身无序二分查找不能用。必须先排序而排序的时间复杂度是 O(n log n)如果整个任务只搜索一次那不如直接 O(n) 线性扫一遍尤其是数据量不大的时候。如果是链表结构即使链表有序也不适合二分查找。链表不支持 O(1) 随机访问取中间元素需要从头遍历整体复杂度退化为 O(n log n)还不如直接遍历。如果数据频繁插入和删除维护有序数组的成本很高。每次插入都要移动元素这时应该考虑平衡二叉树、跳表、堆等动态数据结构而不是用二分查找搭配数组。2.3 使用边界与合规提醒二分查找本身没有任何安全和版权风险但如果在实际业务中使用要注意数据来源的合法性问题。比如对用户数据、日志数据、爬虫采集到的数据做检索时必须确保数据获取方式符合平台规则和相关法律法规。涉及个人信息时要先完成脱敏处理。算法只是工具数据处理流程里的合规问题同样重要。3. 环境准备与前置条件二分查找对运行环境的要求极低几乎任何能跑 Python 的环境都可以。3.1 操作系统与 Python 版本Windows / macOS / Linux 均可。Python 3.6 及以上版本即可建议使用 Python 3.8。不需要安装第三方库标准库bisect已经覆盖工程场景。3.2 运行方式最简单的验证方式是准备一个.py文件然后在终端执行python binary_search_demo.py如果是刚接触 Python还没装好环境可以参考以下步骤快速搭建。3.3 Python 安装检查在终端执行python --version如果提示command not found说明 Python 还没加入环境变量。Windows 用户在安装 Python 时勾选 Add Python to PATH重新打开终端后再检查。macOS 用户可以用python3 --version检查。Linux 用户一般自带 Python 3也可以直接执行python3 --version。3.4 编辑器选择日常练习随便用PyCharm、VS Code、IDLE、Jupyter Notebook 都可以。如果主要在本地写算法题推荐 VS Code Python 插件调试时可以直接查看变量变化对理解边界条件很有帮助。建议先创建一个专门存放算法练习的目录例如mkdir -p ~/algorithm_practice cd ~/algorithm_practice4. 二分查找基础实现二分查找的写法可以有很多种但核心就一句话维护一个左闭右闭或左闭右开的搜索区间每次取中间元素与目标值比较得到结果后缩小区间。两种区间写法对应不同的循环条件、区间更新方式很多人写错就是两种写法混用了。4.1 左闭右闭写法左闭右闭写法的区间是[left, right]left和right指向的元素都在搜索范围内因此循环条件是while left right。当left right时搜索区间为空。def binary_search(nums: list[int], target: int) - int: left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1几个关键细节mid left (right - left) // 2而不是(left right) // 2前者能避免极端情况下left right整数溢出Python 里这个顾虑不大但是好习惯。当nums[mid] target时说明中间值太小目标值一定在右半区所以left mid 1。当nums[mid] target时说明中间值太大目标值一定在左半区所以right mid - 1。循环结束后返回-1表示没有找到。测试一下nums [1, 3, 5, 7, 9, 11, 13] print(binary_search(nums, 7)) # 预期输出 3 print(binary_search(nums, 4)) # 预期输出 -14.2 左闭右开写法左闭右开写法的区间是[left, right)right指向的元素不在搜索范围内因此循环条件是while left right。当left right时区间已经为空。def binary_search_right_open(nums: list[int], target: int) - int: left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid return -1这里最容易写错的就是right mid。因为区间是左闭右开mid已经不可能是目标值时right应该收缩到mid保证[left, right)仍然覆盖真正的搜索区间。4.3 递归写法递归写法在思路上更直观但实际工程中不建议频繁使用因为栈深度受限制。数据量很大时可能出现递归深度超出 Python 默认限制的问题。这里给出一个参考版本def binary_search_recursive(nums: list[int], target: int, left: int, right: int) - int: if left right: return -1 mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: return binary_search_recursive(nums, target, mid 1, right) else: return binary_search_recursive(nums, target, left, mid - 1)4.4 手写二分还是用 bisect如果只是做算法练习手写一遍非常有必要能帮助你理解边界。但在生产代码里更推荐直接用 Python 标准库的bisect。原因很简单标准库实现经过大量测试边界情况处理得比较稳且代码更易读。后面的章节会专门讲bisect的用法。5. 二分查找变体边界查找基础版二分查找能解决“找是否存在某个值”的问题但真实业务里更常见的是“找第一个大于等于目标值的位置”“找最后一个等于目标值的位置”这类边界问题。这类问题最容易出错也是面试高频考点。5.1 查找第一个等于目标值的位置如果有重复元素基础版二分查找返回的可能是任意一个等于目标值的位置。要找到“第一个”需要在nums[mid] target时不直接返回而是继续向左搜索。def find_first_equal(nums: list[int], target: int) - int: left, right 0, len(nums) - 1 result -1 while left right: mid left (right - left) // 2 if nums[mid] target: result mid right mid - 1 elif nums[mid] target: left mid 1 else: right mid - 1 return result执行逻辑是找到目标值时记录当前索引然后把right收缩到mid - 1继续看看左边还有没有。循环结束后result就是最左边的目标值索引。5.2 查找最后一个等于目标值的位置方法与上面对称找到目标值时记录索引然后继续向右搜索。def find_last_equal(nums: list[int], target: int) - int: left, right 0, len(nums) - 1 result -1 while left right: mid left (right - left) // 2 if nums[mid] target: result mid left mid 1 elif nums[mid] target: left mid 1 else: right mid - 1 return result5.3 查找第一个大于等于目标值的位置这个变体在工程里非常常用比如要在有序列表中插入一个元素使列表仍然有序就应该用这个逻辑。bisect_left的底层原理就是这个。def find_first_ge(nums: list[int], target: int) - int: 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返回的是第一个不小于target的索引。如果所有元素都小于target返回len(nums)表示应该插入在末尾。5.4 查找最后一个小于等于目标值的位置def find_last_le(nums: list[int], target: int) - int: left, right 0, len(nums) - 1 result -1 while left right: mid left (right - left) // 2 if nums[mid] target: result mid left mid 1 else: right mid - 1 return result这几个变体互相之间只差一两个条件。建议把这四段代码手动敲一遍然后放到本地跑几个用例重点观察循环结束后的索引位置。6. 使用 Python 内置 bisect 模块手写二分是理解原理工程中直接用bisect才是高效做法。bisect是 Python 标准库不需要安装导入就能用。import bisect6.1 核心函数函数名作用返回值bisect_left(a, x, lo0, hilen(a))返回插入 x 后仍然有序的最左侧位置第一个大于等于 x 的索引bisect_right(a, x, lo0, hilen(a))返回插入 x 后仍然有序的最右侧位置第一个大于 x 的索引insort_left(a, x, lo0, hilen(a))在左边界位置插入 x无insort_right(a, x, lo0, hilen(a))在右边界位置插入 x无bisect_left和bisect_right的区别在有重复元素时最明显。import bisect nums [1, 3, 3, 3, 5, 7, 9] print(bisect.bisect_left(nums, 3)) # 输出 1 print(bisect.bisect_right(nums, 3)) # 输出 4bisect_left(nums, 3)返回第一个值为 3 的位置索引是 1。bisect_right(nums, 3)返回最后一个值为 3 的位置的下一个位置索引是 4。用这两个函数可以很方便地完成很多操作。6.2 用 bisect 判断元素是否存在有重复元素时判断元素是否存在不能用bisect_left直接判断索引是否命中因为bisect_left总是返回一个插入位置。标准做法是def contains(nums: list[int], target: int) - bool: pos bisect.bisect_left(nums, target) return pos len(nums) and nums[pos] target6.3 用 bisect 统计重复元素个数def count_occurrences(nums: list[int], target: int) - int: left bisect.bisect_left(nums, target) right bisect.bisect_right(nums, target) return right - left6.4 用 bisect 维护有序插入import bisect sorted_list [1, 3, 5, 7, 9] bisect.insort(sorted_list, 6) print(sorted_list) # 输出 [1, 3, 5, 6, 7, 9]insort的底层就是先找出插入位置再执行列表插入操作。注意list.insert是 O(n) 操作所以如果插入非常频繁且数据量很大bisect.insort并不适合作为高性能方案这时应该考虑数据结构层面的优化。7. 二分查找性能测试与对比方法二分查找的优势是 O(log n)。为了直观感受可以写一个简单脚本对比线性查找和二分查找在相同数据上的比较次数。7.1 统计比较次数def linear_search_count(nums: list[int], target: int) - int: count 0 for num in nums: count 1 if num target: break return count def binary_search_count(nums: list[int], target: int) - int: left, right 0, len(nums) - 1 count 0 while left right: count 1 mid left (right - left) // 2 if nums[mid] target: break elif nums[mid] target: left mid 1 else: right mid - 1 return count nums list(range(1000000)) print(linear_search_count(nums, 999999)) # 线性查找需要 1000000 次比较 print(binary_search_count(nums, 999999)) # 二分查找通常只需要约 20 次比较这段代码不会影响性能只是一个观察方式。真正工程里评估性能应该用timeit模块对多次调用求平均import timeit import bisect nums list(range(1000000)) target 999999 linear_time timeit.timeit(lambda: target in nums, number100) binary_time timeit.timeit(lambda: bisect.bisect_left(nums, target), number100) print(flinear: {linear_time:.4f}s) print(fbinary: {binary_time:.4f}s)不同机器上运行结果会有差异但整体趋势很明确数据量越大二分查找的优势越明显。7.2 为什么 mid 要写成 left (right - left) // 2很多讲解直接给出这个写法但没解释原因。其实核心原因是防溢出。在 C 或 Java 中left right可能超过整数范围导致计算错误。Python 的整数可以无限大所以这个问题不明显但保持这个写法能保证算法代码在不同语言间迁移时仍然正确。7.3 二分查找对数据规模的要求二分查找比较次数约为log2(n)次。数据量从 1000 增长到 100 万二分查找的比较次数只从约 10 次增长到约 20 次。这就是 O(log n) 的含义。理解这个增长曲线比单纯记住复杂度公式更有用。8. 二分查找经典问题与解题思路理解了基础和边界写法后直接刷一遍 LeetCode 的高频题目效果比看十篇教程更好。下面列出的题目覆盖了二分查找最常见的几种考法。8.1 LeetCode 704 二分查找最基础的题目直接套左闭右闭模板即可。这道题的意义是检验你能不能一次写对循环条件。def search(nums: list[int], target: int) - int: left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -18.2 LeetCode 35 搜索插入位置要求返回目标值在有序数组中的索引如果不存在则返回应该插入的位置。这题其实就是bisect_left的逻辑。def search_insert(nums: list[int], target: int) - int: left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return left8.3 LeetCode 34 在排序数组中查找元素的第一个和最后一个位置这道题是变体的直接应用分别找第一个等于 target 和最后一个等于 target 的索引。def search_range(nums: list[int], target: int) - list[int]: def find_left(): left, right 0, len(nums) - 1 result -1 while left right: mid left (right - left) // 2 if nums[mid] target: result mid right mid - 1 elif nums[mid] target: left mid 1 else: right mid - 1 return result def find_right(): left, right 0, len(nums) - 1 result -1 while left right: mid left (right - left) // 2 if nums[mid] target: result mid left mid 1 elif nums[mid] target: left mid 1 else: right mid - 1 return result return [find_left(), find_right()]也可以用bisect_left和bisect_right简写但面试时建议先手写一遍再提标准库方案。8.4 LeetCode 278 第一个错误的版本这题的难点在于理解“版本数组”实际上是[False, False, ..., True, True]这样的结构要找第一个 True。直接用左闭右开模板。def first_bad_version(n: int) - int: left, right 1, n while left right: mid left (right - left) // 2 if is_bad_version(mid): right mid else: left mid 1 return left8.5 LeetCode 153 寻找旋转排序数组中的最小值旋转数组的特点是数组原本有序但在某个点旋转了。最小值左边的元素都大于右边。可以二分查找最小值位置。def find_min(nums: list[int]) - int: left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] nums[right]: left mid 1 else: right mid return nums[left]8.6 LeetCode 162 寻找峰值峰值元素是大于左右相邻元素的元素。由于相邻元素不相等可以二分查找。def find_peak_element(nums: list[int]) - int: left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] nums[mid 1]: left mid 1 else: right mid return left8.7 二分答案思想有些问题不是直接在一个数组里二分而是在答案的取值范围上二分。比如给定一个数组和一个整数 k问能否在 k 次操作内让数组中的最大值最小。给定一个正整数 x求 x 的平方根整数部分。这类题目的套路是先确定答案的上下界然后写一个check(mid)函数判断当前答案是否可行再根据check的结果调整区间。def my_sqrt(x: int) - int: left, right 0, x while left right: mid left (right - left) // 2 if mid * mid x: left mid 1 else: right mid - 1 return right这道题把所有可能的整数根当作搜索空间对每个 mid 判断mid * mid是否小于等于 x最后返回最大的满足条件的结果。二分答案思想的应用范围比“在数组中查找元素”广得多。遇到“最大值最小”“最小值最大”这类说法时第一反应就应该是二分答案。9. 二分查找常见问题与排查方法写二分查找时常见的坑其实就集中在几个位置。下面把这些坑统一列成排查表。问题现象可能原因排查方式解决方案循环永不结束区间更新条件写错打印每次更新后的 left、right、mid左闭右闭写法中left mid 1或right mid - 1左闭右开写法中left mid 1或right mid返回结果差一位区间开闭混乱检查循环条件和更新条件是否匹配写代码时先确定区间类型全程保持一致数组越界未判断mid或返回索引是否在范围内检查mid计算和返回位置结合left、right考虑边界索引是否有效有重复元素时结果不唯一没有特殊处理边界用bisect_left和bisect_right验证按题目要求写边界变体mid计算溢出left right可能超大检查写的是left (right - left) // 2还是(left right) // 2统一用left (right - left) // 2递归深度超出限制递归写法数据量过大查看报错信息改用迭代写法LeetCode 提交报错边界条件未覆盖空数组或单元素数组尝试nums[]、nums[1]等用例在函数开头处理空数组情况9.1 空数组处理基础版二分查找里len(nums) - 1在空数组时会得到-1此时left0, right-1循环条件不成立直接返回-1逻辑没问题。但如果你写的是左闭右开写法right len(nums)空数组时right 0left right不成立也会返回-1。所以大多数模板对空数组是天然安全的。不过为了可读性建议在函数入口加一行if not nums: return -19.2 打印调试法刚开始学二分查找时如果死活找不到 bug不要盯着代码空想。直接在循环里打印中间变量。while left right: mid left (right - left) // 2 print(fleft{left}, right{right}, mid{mid}, nums[mid]{nums[mid]})观察每一轮区间是怎么收缩的很快就能定位是条件写反了还是区间收窄方式错了。10. 最佳实践与代码模板10.1 标准左闭右闭模板def binary_search(nums: list[int], target: int) - int: if not nums: return -1 left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -110.2 标准左闭右开模板def binary_search(nums: list[int], target: int) - int: if not nums: return -1 left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid return -110.3 工程建议生产环境优先用bisect不要自己造轮子。只有在算法面试或特殊需求下才手写。手写时选定一种区间开闭方式整个函数保持统一不要混用。每次写完测试三个边界用例空数组、单元素数组、目标值在数组首位或末位。把常用变体封装成函数放在自己的工具模块里例如“第一个大于等于”“最后一个小于等于”。面试时先和面试官确认区间写法再用模板写代码最后口头解释边界条件会让表达更清楚。10.4 一个可复用的工具库示例import bisect def first_ge(nums: list[int], target: int) - int: return bisect.bisect_left(nums, target) def first_gt(nums: list[int], target: int) - int: return bisect.bisect_right(nums, target) def last_le(nums: list[int], target: int) - int: pos bisect.bisect_right(nums, target) return pos - 1 if pos 0 else -1 def last_lt(nums: list[int], target: int) - int: pos bisect.bisect_left(nums, target) return pos - 1 if pos 0 else -1这几个函数本质上都是bisect_left和bisect_right的排列组合理解了之后可以直接组合出各种边界查询。11. 总结与下一步二分查找最值得花时间的地方不是背模板而是理解区间开闭和边界条件。建议你先手动敲一遍左闭右闭和左闭右开两个版本然后跑一下 704、35、34、278、153、162 这几道 LeetCode 题看看自己会在哪里出错再回来看本文第 5 节和第 9 节定位问题会很快。最容易踩的坑就是混用区间写法循环条件用的是更新边界时却用了right mid或者反过来。记住一个原则——先确定区间类型再写循环条件和更新语句全程保持一致。下一步可以往两个方向继续深入一是把二分查找和三分查找、二分答案放到一起对比学习理解二分思想在更多问题中的应用二是结合bisect标准库在自己的 Python 项目中应用有序列表的批量插入和区间查询能力。把二分查找从“会背模板”变成“能灵活变体”很多算法题的思路会顺很多。