之前在业务开发里处理有序数据的查找时我频繁踩到二分查找的边界坑要么死循环要么漏掉目标元素要么返回的下标不对。排查半天发现问题往往出在left和right的更新逻辑上。其实二分查找本身并不难难的是把边界条件和循环不变量写清楚。这篇文章围绕 Python 中的二分查找进行一次完整整理从原理推导、手写实现、标准库使用到典型变体和常见坑点逐步展开适合刚接触算法的 Python 初学者也适合需要用二分查找解决实际问题的开发者。学完后你能独立写出正确的迭代版和递归版二分查找能熟练使用bisect模块处理有序数组也能应对“查找左边界”“查找右边界”“查找插入位置”这几类高频面试和工程场景。1. 二分查找是什么为什么需要它1.1 一个最朴素的需求假设我们有一个已经按从小到大排好序的数组nums [1, 3, 5, 7, 9, 11, 13, 15]我们想知道数字7是否存在于数组中并返回它的下标。最直接的想法是从头到尾遍历def linear_search(nums, target): for i, num in enumerate(nums): if num target: return i return -1这个方法当然正确但它有一个明显的问题如果数组有 100 万个元素而目标值排在最后最坏情况下要比较 100 万次。这种逐个扫描的方式时间复杂度是 O(n)。当数据量变大、查询次数变多时性能压力会非常明显。1.2 二分查找的核心思想二分查找Binary Search是一种针对有序数组的查找算法。它的思路和我们平时翻字典很像字典的单词是按字母顺序排列的想查找一个单词时不会从第一页翻到最后一页而是先翻到中间根据字母顺序判断目标在左半部分还是右半部分然后继续在对应的一半中重复这个过程。用专业一点的话说二分查找每次将查找区间缩小一半通过比较中间元素与目标值的大小关系排除掉不可能是答案的那一半区间。由于每轮都能排除一半数据它的时间复杂度是 O(log n)。对于 100 万个元素线性查找最坏需要 100 万次比较而二分查找最多只需要约 20 次比较差距非常明显。1.3 适用条件二分查找虽然高效但不是所有场景都能用。它有两个关键前提数据必须是有序的通常是单调递增或单调递减数据需要支持随机访问也就是可以通过下标直接获取元素Python 的列表满足这个条件。如果数据本身无序需要先排序才能使用二分查找。排序本身有 O(n log n) 的开销所以如果只是单次查询排序后二分查找不一定比线性查找快但如果数据会反复查询那么排序一次、查询多次二分查找就有很大优势。1.4 常见应用场景二分查找不只是用来“查一个数在不在数组里”它在实际开发中还有不少应用场景场景说明有序数组查找判断目标值是否存在返回下标查找插入位置在有序数组中插入新元素找到应插入的位置查找左边界数字可能重复查找第一次出现的位置查找右边界数字可能重复查找最后一次出现的位置数值逼近求平方根、求解单调函数的根等旋转数组查找有序数组旋转后仍可用二分思想查找目标算法竞赛中的二分答案将最优化问题转化为判定问题从这些场景能看到二分查找不仅是一个基础算法更是一种解决问题的思维模式。2. 环境准备与版本说明本文代码基于 Python 3 编写。Python 2 已经停止维护不推荐继续使用。示例代码中用到的语法和标准库在 Python 3.6 以上版本都能正常运行。如果你还没有配置好 Python 环境可以参考下面的建议操作系统Windows / macOS / Linux 均可Python 版本建议 3.8 及以上版本差异对本文内容影响很小IDEPyCharm、VS Code 或直接使用命令行交互环境都可以标准库本文会用到一个内置模块bisect它是 Python 自带的不需要额外安装。验证环境是否可用的方式很简单在命令行或 IDE 中运行python --version如果输出类似Python 3.10.0这样的信息说明环境正常。接下来我们直接在 Python 文件中写代码即可不需要创建复杂的工程结构。3. 二分查找的原理拆解3.1 循环不变量写对二分查找的关键是理解一个概念循环不变量。简单来说它表示在每一轮循环开始之前我们都要明确“目标值可能存在的区间”是什么。最常见的写法用两个指针left表示查找区间左端点right表示查找区间右端点。在区间[left, right]中我们要维护这样一个性质目标值如果存在一定在这个闭区间内。每一轮循环我们取中间位置mid (left right) // 2然后比较nums[mid]和target的大小如果nums[mid] target说明找到了直接返回mid如果nums[mid] target说明目标值只可能在mid右侧下一轮把left更新为mid 1如果nums[mid] target说明目标值只可能在mid左侧下一轮把right更新为mid - 1。这里有一个非常容易出错的点为什么是mid 1和mid - 1而不是mid因为nums[mid]已经和target比较过了它不可能是我们要找的目标所以新的区间应该排除掉mid这个位置。如果写成left mid或right mid在特定条件下会导致区间始终无法缩小程序陷入死循环。3.2 循环条件的选择循环条件有两种常见写法分别对应不同的区间定义写法一区间为[left, right]闭区间循环条件为left right。def binary_search(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1当left right时说明区间已经为空目标值不存在返回 -1。写法二区间为[left, right)左闭右开区间循环条件为left right。def binary_search_2(nums, target): left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid return -1注意这里的区别右端点初始值是len(nums)而不是len(nums) - 1更新right时是right mid而不是right mid - 1。这是因为right本身不参与区间的包含它只是一个开区间边界。两种写法都能实现二分查找建议初学者先熟练掌握其中一种然后再理解另一种。我个人更推荐第一种闭区间写法它的边界处理更直观很多教程也是基于这种方式展开的。3.3 中间位置的计算中间位置通常写为(left right) // 2。这种写法在大多数情况下没有问题。不过在算法竞赛或极端数据量场景下left right可能超出整数上限更稳妥的写法是mid left (right - left) // 2Python 的整数是任意精度普通业务中两种写法都没问题但养成使用第二种写法的习惯可以避免在 C 或 Java 等语言中遇到整数溢出的问题。从工程习惯的角度来说两种都可以但理解left (right - left) // 2的含义有助于加深对区间长度的理解。4. 完整实战手写二分查找与标准库使用4.1 创建项目结构我们用一个简单的 Python 文件来演示完整流程不需要复杂的工程结构。项目目录如下binary_search_demo/ ├── binary_search_impl.py └── main.py其中binary_search_impl.py存放我们自己实现的二分查找函数main.py是测试入口。4.2 编写核心代码首先实现迭代版二分查找。新建binary_search_impl.py写入以下代码# 文件路径binary_search_demo/binary_search_impl.py def binary_search(nums, target): 在有序数组中查找目标值。 如果找到返回目标值的下标否则返回 -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 -1接着实现递归版二分查找。递归版本更接近数学定义适合用来理解算法思想但在 Python 中递归调用会占用函数调用栈数据量很大时不如迭代版稳妥# 文件路径binary_search_demo/binary_search_impl.py def binary_search_recursive(nums, target, left, right): 递归版二分查找。 调用方式binary_search_recursive(nums, target, 0, len(nums) - 1) 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)再实现一个查找插入位置的函数。这个函数要回答一个问题如果要把target插入有序数组中它应该放在哪个下标比如数组[1, 3, 5]要插入4结果应该是下标 2因为插入后数组变成[1, 3, 4, 5]4的下标是 2# 文件路径binary_search_demo/binary_search_impl.py def search_insert_position(nums, target): 返回 target 应该插入的位置。 如果 target 已存在返回它当前所在的位置。 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 left这段代码的返回值是left。为什么是left因为循环结束时的条件是left right此时left指向的位置正好是第一个大于等于目标值的位置也就是插入位置。这个结论可以通过几个简单的例子验证。最后我们来看 Python 标准库bisect。它是 Python 内置的二分查找模块性能经过 C 语言实现优化实际工程中优先使用它而不是自己手写# 文件路径binary_search_demo/binary_search_impl.py import bisect def standard_bisect_demo(nums, target): 演示 bisect 模块的常用方法。 bisect_left返回插入位置如果 target 已存在返回左侧第一个位置。 bisect_right返回插入位置如果 target 已存在返回右侧第一个位置。 left_index bisect.bisect_left(nums, target) right_index bisect.bisect_right(nums, target) return left_index, right_indexbisect_left和bisect_right的区别在数组元素有重复时非常关键。举例来说nums [1, 3, 3, 3, 5] target 3bisect_left(nums, 3)返回 1也就是第一个3的位置bisect_right(nums, 3)返回 4也就是最后一个3后面的位置。因此如果要查找目标值在数组中出现的区间可以用bisect_left和bisect_right配合实现。4.3 编写测试入口在main.py中编写测试代码验证上面的函数是否正常# 文件路径binary_search_demo/main.py from binary_search_impl import ( binary_search, binary_search_recursive, search_insert_position, standard_bisect_demo, ) import bisect def main(): nums [1, 3, 5, 7, 9, 11, 13, 15] targets [7, 4, 0, 15, 16] print(测试数组:, nums) print(- * 40) for target in targets: idx binary_search(nums, target) print(f迭代版查找 {target}: 结果是 {idx}) print(- * 40) for target in targets: idx binary_search_recursive(nums, target, 0, len(nums) - 1) print(f递归版查找 {target}: 结果是 {idx}) print(- * 40) for target in targets: pos search_insert_position(nums, target) print(f插入位置查询 {target}: 结果下标是 {pos}) print(- * 40) nums_with_repeat [1, 3, 3, 3, 5, 7] for target in [3, 4]: li bisect.bisect_left(nums_with_repeat, target) ri bisect.bisect_right(nums_with_repeat, target) print(fbisect 模块 target{target}: bisect_left{li}, bisect_right{ri}) if __name__ __main__: main()4.4 运行与验证在binary_search_demo目录下执行python main.py预期输出如下测试数组: [1, 3, 5, 7, 9, 11, 13, 15] ---------------------------------------- 迭代版查找 7: 结果是 3 迭代版查找 4: 结果是 -1 迭代版查找 0: 结果是 -1 迭代版查找 15: 结果是 7 迭代版查找 16: 结果是 -1 ---------------------------------------- 递归版查找 7: 结果是 3 递归版查找 4: 结果是 -1 递归版查找 0: 结果是 -1 递归版查找 15: 结果是 7 递归版查找 16: 结果是 -1 ---------------------------------------- 插入位置查询 7: 结果下标是 3 插入位置查询 4: 结果下标是 3 插入位置查询 0: 结果下标是 0 插入位置查询 15: 结果下标是 7 插入位置查询 16: 结果下标是 8 ---------------------------------------- bisect 模块 target3: bisect_left1, bisect_right4 bisect 模块 target4: bisect_left5, bisect_right5验证一下结果是否符合预期目标值7在数组下标 3 处迭代版和递归版都返回 3目标值4、0、16不在数组中返回 -1目标值15在数组下标 7 处返回 7插入位置查询时4应该插到下标 3因为[1, 3, 4, 5, ...]中 4 比 3 大、比 5 小16比所有元素都大应该插到下标 8也就是数组末尾bisect_right在目标值有重复时返回的是重复段右侧的位置。4.5 结果分析从运行结果可以看到迭代版和递归版结果一致。但两者在实际工程中的选择有讲究迭代版没有递归栈深度限制性能更高是推荐的生产写法递归版代码更贴近算法定义适合学习和做二叉搜索树相关题目时理解递归思想在 Python 中直接使用bisect是最简洁的方案查找和插入位置的操作都能一行完成而且底层是 C 实现的速度比纯 Python 手写快很多。5. 常见问题与排查思路二分查找最常见的三类问题基本都集中在边界条件上。下面用表格整理高频问题及其解决思路。问题现象常见原因解决思路程序陷入死循环left或right更新成了mid区间没有缩小将更新改为mid 1或mid - 1确保每轮区间长度严格递减查找目标存在但返回 -1循环条件写成了left right导致最后一个元素没比较确认使用的区间是闭区间还是左闭右开区间并配套正确的循环条件返回的下标比正确值大 1 或少 1right初始值写成了len(nums)却按闭区间逻辑更新统一区间定义闭区间初始化为len(nums) - 1左闭右开初始化为len(nums)重复元素时定位不到第一个或最后一个只判断了等值没有继续向左右收缩使用bisect_left和bisect_right或手写边界收缩逻辑mid计算溢出left right超过整数上限使用left (right - left) // 25.1 复现一个死循环场景来看一个典型的死循环写法def wrong_binary_search(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: left mid elif nums[mid] target: right mid else: return mid return -1问题在于当nums[mid] target时mid位置的值小于目标值理论上mid不可能是答案但如果把left更新为mid而不是mid 1当区间长度为 2 时会出现left和mid相等的情况下一轮循环区间不再缩小于是死循环。例如数组[1, 3]查找目标3初始left0right1mid0nums[0]1 3执行left mid 0下一轮mid还是 0left仍是 0循环无法退出。排查这类问题时可以在循环中打印left、right、mid三个变量的值观察区间是否在每轮缩小。如果连续多轮三个值都没有变化几乎可以确定是更新逻辑写错了。5.2 元素不存在与返回 -1 的判断很多初学者会把“循环结束返回 -1”写在错误的位置。正确的逻辑是只有在循环结束后才能确定目标值不存在。如果在循环内部提前返回 -1会导致后续可查找区间被错误跳过。例如下面这种写法def wrong_return(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid if nums[mid] target: left mid 1 else: right mid - 1 if left len(nums) - 1: return -1 return -1这段代码虽然多数情况下能工作但left len(nums) - 1的判断冗余且容易掩盖问题。更清晰的写法是循环结束后统一返回 -1不在循环内部增加额外的返回分支。5.3 重复元素的处理假设数组是[1, 2, 2, 2, 3]我们要找第一个2的下标和最后一个2的下标。如果只是用普通二分查找返回的可能是任意一个等于目标值的下标而不一定是第一个或最后一个。为了定位边界需要在元素相等时继续收缩搜索区间查找第一个等于目标值的下标当nums[mid] target时不直接返回而是把right更新为mid - 1继续在左半部分查找查找最后一个等于目标值的下标当nums[mid] target时把left更新为mid 1继续在右半部分查找。不过实际工程中直接用bisect_left和bisect_right更省事。bisect_left得到的就是第一个等于目标值的位置bisect_right - 1得到的就是最后一个等于目标值的位置。import bisect nums [1, 2, 2, 2, 3] target 2 left_index bisect.bisect_left(nums, target) right_index bisect.bisect_right(nums, target) - 1 print(left_index) # 1 print(right_index) # 3如果bisect_left和bisect_right返回相同的位置说明目标值在数组中不存在。6. 最佳实践与工程建议6.1 优先使用标准库Python 标准库bisect已经提供了经过优化的二分查找实现日常开发中应该优先使用。它不仅能查找元素还能在保持数组有序的前提下执行插入操作常用的方法有方法作用bisect.bisect_left(a, x)返回 x 在有序列表 a 中的插入位置如果 x 已存在返回左侧位置bisect.bisect_right(a, x)返回 x 在有序列表 a 中的插入位置如果 x 已存在返回右侧位置bisect.insort_left(a, x)在 a 中按有序位置插入 x插入到相同元素的左侧bisect.insort_right(a, x)在 a 中按有序位置插入 x插入到相同元素的右侧需要注意的是insort系列方法的插入操作是 O(n) 的因为列表中间插入元素需要移动后续元素。如果频繁插入和查找并存应该考虑使用bisect配合其他数据结构或者在设计阶段评估性能要求。6.2 明确区间的定义无论手写还是阅读别人的二分查找代码第一件事都是确认代码使用的是闭区间还是左闭右开区间。如果不明确区间定义很容易在修改代码时产生新的边界 bug。一个实用的建议是在函数注释中写明区间定义。def binary_search(nums, target): 在有序数组 nums 中查找 target。 使用闭区间 [left, right]。 返回目标值下标不存在时返回 -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 -1清晰的注释能显著降低后续维护成本尤其是在团队协作中。6.3 考虑空数组和单元素数组边界条件测试是二分查找最容易踩坑的地方。不管手写还是使用标准库都要测试下面几种输入print(binary_search([], 5)) # 空数组应返回 -1 print(binary_search([5], 5)) # 单元素命中应返回 0 print(binary_search([5], 3)) # 单元素未命中应返回 -1 print(binary_search([1, 2], 1)) # 两个元素命中左端点应返回 0 print(binary_search([1, 2], 2)) # 两个元素命中右端点应返回 1 print(binary_search([1, 2], 3)) # 大于所有元素应返回 -1空数组场景下len(nums) - 1等于 -1此时left0right-1循环条件left right不成立直接返回 -1所以实现是正确的。但如果写成while left right空数组时也不会进入循环返回 -1同样正确。无论哪种写法都要单独验证这类边界输入。6.4 与排序配合时的注意点如果数据本身无序在使用二分查找前需要先排序。但排序会改变元素顺序如果后续还需要知道元素在原数组中的位置排序前就要记录原始下标。一个常见思路是用enumerate把元素和下标组成元组后再排序nums [5, 3, 8, 1, 9] indexed_nums sorted((num, idx) for idx, num in enumerate(nums)) print(indexed_nums) # [(1, 3), (3, 1), (5, 0), (8, 2), (9, 4)]这样排序后的每个元组都保留了原始下标查找结果可以直接映射回原数组位置。6.5 理解二分答案思想除了在数组中查找元素二分查找更进阶的用法是“二分答案”。它适用于这样的场景某个问题的“答案”是单调的比如“满足条件的最小值”“满足条件的最大值”。此时可以把问题转化为判定问题用二分枚举答案再验证当前答案是否可行。一个典型例子是求一个数的整数平方根。比如计算x的整数平方根也就是最大的n满足n * n xdef integer_sqrt(x): if x 0: raise ValueError(不能对负数求平方根) left, right 0, x ans -1 while left right: mid left (right - left) // 2 if mid * mid x: ans mid left mid 1 else: right mid - 1 return ans运行测试print(integer_sqrt(9)) # 3 print(integer_sqrt(10)) # 3 print(integer_sqrt(16)) # 4 print(integer_sqrt(1)) # 1 print(integer_sqrt(0)) # 0这类使用方式在算法题和工程计算中都很常见理解了二分查找的核心逻辑后再学习二分答案会顺畅很多。7. 学习路线与后续方向7.1 本文核心要点回顾到这里我们已经完成了从原理到实战的完整学习。需要熟练掌握的内容包括二分查找解决的问题是“在有序数组中高效查找目标”时间复杂度 O(log n)手写二分查找时要明确闭区间还是左闭右开区间并正确配套循环条件和指针更新逻辑mid的计算建议使用left (right - left) // 2迭代版是生产环境的首选递归版主要用于理解递归思想Python 标准库bisect覆盖了查找和插入位置两大能力建议优先使用重复元素场景下bisect_left和bisect_right能分别定位左边界和右边界任何手写实现都要测试空数组、单元素数组、目标值大于所有元素、目标值小于所有元素、重复元素这些边界场景。7.2 下一步可以继续学什么掌握了基础二分查找后下面几个方向值得继续深入学习方向学习内容二分查找变体查找第一个大于等于目标值的元素、查找最后一个小于等于目标值的元素旋转有序数组在[5, 6, 7, 1, 2, 3]这类旋转数组中查找目标值二分答案将最优化问题转化为判定问题例如“最小化最大值”“最大化最小值”数据结构配合有序列表维护、SortedList第三方库、树状数组与二分结合算法竞赛常用技巧浮点数二分的精度控制、单调函数求解推荐在 LeetCode 上搜索“二分查找”标签从简单题入手逐步过渡到中等难度题目。刷题时不要只看题解要自己把区间、边界和返回值推演一遍尤其是要把每个变体的循环不变量写清楚这样才能在代码里游刃有余。7.3 实际项目中的优先级在实际项目中使用二分查找优先级可以这样排列优先使用标准库bisect代码简洁性能可靠需要自定义特殊逻辑时再手写且必须写好注释和边界测试每次改动二分查找逻辑都要重新跑一遍边界样例和随机对比测试如果数组频繁插入删除不要依赖insort的单次效率要评估整体数据结构的合理性。二分查找看似简单但每一年面试和笔试中仍然有大量候选人因为边界条件写错而失分。它不是“背模板”就能一劳永逸的算法真正掌握的标准是能在不看参考代码的情况下写出正确处理重复元素、空数组、目标值不存在等场景的实现并能清楚解释每一步为什么这么写。建议你打开编辑器先自己独立写一遍普通二分查找再尝试写左边界和右边界版本最后用bisect模块完成同样的功能。实践三到五遍之后相关的边界习惯自然就会内化。遇到报错也不用着急把left、right、mid三个变量打印出来逐步推演区间变化绝大多数问题都能很快定位。