在处理有序数组时二分查找是 Python 程序员必须掌握的基础算法之一。它的核心思想很简单每次取数组中间位置的值与目标值比较根据比较结果排除一半数据从而把查找范围快速缩小。真正的问题不在思想而在实现边界。很多初学者在纸上能把流程画清楚一写代码却容易出现死循环、漏检、返回值对不上的情况。这篇内容围绕“二分查找有序数组”这条主线展开。先讲清楚它解决什么问题、适用条件是什么再给出可运行的 Python 代码然后重点拆解区间写法、中间值计算、边界收缩这类容易出错的地方最后补充进阶场景、测试用例、常见坑和工程封装建议。学完之后你不仅能手写经典二分查找也能处理重复元素、查找左右边界、使用 Python 内置bisect模块并在项目里写出更稳的封装。1. 二分查找到底在解决什么问题1.1 一句话理解二分查找的原理二分查找解决的是一个非常具体的查找问题在一个已经排好序的数组里快速找到目标值的位置。它的做法是每次取当前查找区间的中点把中点值与目标值比较。如果中点值正好等于目标值查找结束。如果中点值小于目标值说明目标值只可能在中点右侧因为数组是升序的反之目标值只可能在中点左侧。这样每一轮都能把查找范围缩小一半所以叫二分查找。举个例子数组[1, 3, 5, 7, 9, 11, 13]目标值是 7第一轮区间下标 0 到 6中间下标 3nums[3] 7直接找到。如果把目标值改为 11第一轮nums[3] 7 11可以排除左侧[1, 3, 5, 7]下一轮只查[9, 11, 13]。这里的关键前提是“已经排好序”。如果数组无序比较中点值后无法判断目标值在左侧还是右侧二分查找就失去意义。1.2 为什么数组必须有序且支持随机访问二分查找成立的前提有两个数组有序并且能够通过下标直接访问任意位置的元素。数组满足随机访问条件所以可以用nums[mid]直接取中间值。如果数据存放在链表中即使链表有序二分查找也不适合因为每次定位中间节点都要从头遍历单步时间从 O(1) 变成 O(n)整体复杂度会退化。类似地如果数据是动态变化的每次插入删除后都要重新排序维护有序的成本需要考虑进去。实际生产中二分查找更常见于排序后的静态数据例如日志按时间排序后查询某时间点附近的记录、价格表区间匹配、评分卡分档命中这类场景。1.3 复杂度分析时间换来的效率提升有多少假设数组长度为 n第一轮比较后剩下 n/2第二轮剩下 n/4重复 k 次后区间长度为 1所以比较次数约为 log2(n)。时间复杂度是 O(log n)空间复杂度是 O(1)迭代版本不需要额外存储。顺序查找最坏要比较 n 次当 n 达到 100 万时顺序查找最多 100 万次比较二分查找只需要约 20 次。数据越大差距越明显。这也是二分查找在有序数组查找场景中始终值得优先考虑的原因。但不要误以为 O(log n) 一定比哈希查找更好。哈希表查找平均也是 O(1)但哈希表无法直接处理“区间查询”“第一个大于等于某个值”这类问题。二分查找的真正优势在于在有序数据上它不仅能查“等不等于”还能查“满足某个条件的边界在哪里”。2. 环境准备和第一版可运行代码2.1 运行环境和准备工作实现二分查找不需要安装第三方库Python 3 标准环境即可。如果你的电脑还没装 Python可以到官网下载对应系统的安装包安装时勾选“Add Python to PATH”装完后在命令行执行python --version能看到版本号说明环境可用。也可以使用 IDE 或编辑器比如 PyCharm 或 VS Code创建项目后新建 Python 文件比如binary_search.py。学习阶段不建议一开始就用复杂脚手架一个文件、一个函数、几个测试用例足够把算法理解清楚。2.2 迭代版基本实现下面是最常见的左闭右闭写法def binary_search(nums, 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 -1这段代码的含义是查找区间从下标 0 到下标len(nums) - 1左右都是闭区间。每一轮都检查中间下标mid。如果中间值小于目标值说明目标值只可能在右半部分于是把左边界移到mid 1如果中间值大于目标值把右边界移到mid - 1。当left right时区间已经为空说明数组中没有目标值返回 -1。这里要解释mid为什么用left (right - left) // 2。在很多语言里直接写(left right) // 2在极端情况下可能溢出用减法再除以 2 更安全。Python 整数虽然没有溢出限制但这个写法能保持同样的可读性和习惯跨语言迁移时也不会踩坑。2.3 递归版实现递归版逻辑与迭代版一致只是把区间参数显式传入def binary_search_recursive(nums, target, left, right): 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)调用方式nums [1, 3, 5, 7, 9] result binary_search_recursive(nums, 5, 0, len(nums) - 1) print(result)输出2递归版在理解上更直观但函数调用会占用额外栈空间。对于非常大的数组递归深度可能成为限制。生产代码更推荐迭代版既能避免递归深度问题也没有不必要的函数调用开销。3. 边界处理是二分查找最容易出错的地方3.1 左闭右闭和左闭右开两种区间写法二分查找有两大流派左闭右闭[left, right]和左闭右开[left, right)。两种写法都能实现关键是必须保持一致。左闭右开写法def binary_search_half_open(nums, target): 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左闭右闭和左闭右开的差异可以用一张表看清楚对比项左闭右闭左闭右开初始右边界len(nums) - 1len(nums)循环条件while left rightwhile left right中间值大于目标时right mid - 1right mid循环退出时区间状态left right区间为空left right区间收敛到一点初学者出错概率容易忘记 -1 或 1容易忘记right mid两种写法都行但不要混用。混用是二分查找死循环最常见的原因之一。3.2 mid 的计算方式为什么影响安全性和可读性计算中间值有三种常见写法mid (left right) // 2 mid left (right - left) // 2 mid left ((right - left) 1)第一种写在 Python 中不会因为整数相加而溢出但缺少通用性。第二种是跨语言最安全的写法推荐使用。第三种用位运算在某些语言里性能略好但可读性不如第二种。还要注意取整方向。// 2是向下取整所以mid会偏向左侧。在左闭右开写法里这能保证当left和right相邻时mid等于left配合left mid 1或right mid可以避免区间无法缩小。3.3 left 和 right 的更新规则决定了算法是否正确不管哪种写法更新规则都要保证区间确实在缩小否则就会死循环。左闭右闭写法当nums[mid] target时left mid 1当nums[mid] target时right mid - 1。因为mid已经比较过不可能再是答案所以可以直接跳过。左闭右开写法当nums[mid] target时left mid 1当nums[mid] target时right mid。这里右边界不能写成mid - 1因为右边界本身不参与区间mid作为新的右边界意味着区间范围是[left, mid)mid仍然大于目标值放在边界外是合理的选择。一个快速检查方法是在循环里打印left、right、mid确认每轮区间长度都在变小。下面是一个临时调试版def binary_search_debug(nums, target): left, right 0, len(nums) - 1 step 0 while left right: mid left (right - left) // 2 print(fstep{step}, left{left}, right{right}, mid{mid}) step 1 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1如果发现某一步left和right没有变化说明更新规则有问题。4. 从查找单个值到查找左右边界4.1 查找第一个等于 target 的位置标准二分查找遇到重复元素时只能保证返回某个等于 target 的下标不一定是第一个。如果需要第一个等于 target 的位置比如“用户第一次登录时间”“订单第一次出现”就要用下面这种写法def find_left_bound(nums, target): 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 的下标。调用后还需要判断这个下标是否合法并且该位置值是否等于 targetdef find_first_equal(nums, target): pos find_left_bound(nums, target) if pos len(nums) and nums[pos] target: return pos return -14.2 查找最后一个等于 target 的位置对称地查找最后一个等于 target 的位置可以先找到第一个大于 target 的位置再往左移动一位def find_right_bound(nums, target): 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 - 1 def find_last_equal(nums, target): pos find_right_bound(nums, target) if pos 0 and nums[pos] target: return pos return -1注意这里判断条件变成了nums[mid] target含义是“把左边界不断向右边推直到越过所有等于 target 的元素”。测试一组重复数据nums [1, 2, 2, 2, 3, 5] print(find_first_equal(nums, 2)) # 1 print(find_last_equal(nums, 2)) # 34.3 查找第一个大于等于或大于 target 的位置在程序设计中这类问题常被称为 lower_bound 和 upper_bounddef lower_bound(nums, target): 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 def upper_bound(nums, target): 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返回值可理解为“插入位置”lower_bound返回 target 应该插入的位置插入后数组仍有序upper_bound返回第一个大于 target 的位置。返回len(nums)表示目标值比所有元素都大。4.4 直接使用 bisect 模块代替手写Python 标准库提供的bisect模块包含了 lower_bound 和 upper_bound 的成熟实现推荐在不需要自定义比较逻辑的生产代码中直接使用from bisect import bisect_left, bisect_right nums [1, 2, 2, 3, 5, 7] print(bisect_left(nums, 2)) # 1 print(bisect_right(nums, 2)) # 3 print(bisect_left(nums, 4)) # 4 print(bisect_right(nums, 4)) # 4用bisect计算重复元素个数count bisect_right(nums, 2) - bisect_left(nums, 2) print(count) # 2bisect不用额外安装属于 Python 标准库这一点在工程里非常省心。5. 用测试用例验证正确性而不是靠肉眼5.1 最小验证用 assert 快速确认写完函数后最简单的验证方式是用断言def test_binary_search(): data [1, 3, 5, 7, 9] assert binary_search(data, 5) 2 assert binary_search(data, 1) 0 assert binary_search(data, 9) 4 assert binary_search(data, 4) -1 assert binary_search(data, 0) -1 assert binary_search([], 1) -1 assert binary_search([1], 1) 0 assert binary_search([1], 2) -1 print(all tests passed) test_binary_search()运行后看到all tests passed说明通过。这一步很快初学者也应该养成写完算法先跑断言的习惯。5.2 用 pytest 覆盖更多输入组合如果想更规范可以安装 pytestpip install pytest把测试写到test_binary_search.pyimport pytest from binary_search import binary_search pytest.mark.parametrize( nums,target,expected, [ ([1, 2, 3, 4, 5], 3, 2), ([1, 2, 3, 4, 5], 0, -1), ([1, 2, 3, 4, 5], 6, -1), ([2, 2, 2], 2, 1), ([], 1, -1), ([1], 1, 0), ], ) def test_binary_search(nums, target, expected): assert binary_search(nums, target) expected然后运行pytest test_binary_search.py -v注意重复元素[2, 2, 2]返回 1 是标准二分查找的合法结果因为中间下标就是 1。如果测试需要稳定答案应该用左边界或右边界函数。5.3 边界用例清单测试时至少要覆盖下列情况用例目的空数组验证不会越界单元素数组命中验证循环条件正确单元素数组未命中验证返回 -1目标值在开头验证左边界收敛目标值在结尾验证右边界收敛目标值不在数组中验证区间收缩直到为空数组有重复元素验证返回语义是否稳定数组长度为奇数基本场景数组长度为偶数验证 mid 取整行为6. 常见错误现象和排查路径6.1 死循环现象、原因和修复现象程序运行很长时间不结束或递归版本直接栈溢出。原因通常是区间没有缩小。典型错误是左闭右开写法里当nums[mid] target时写成right mid - 1或者left mid导致相邻元素时区间无法变化。修复方法先确认区间初始化、循环条件、边界收缩来自同一套写法。再写一个最小用例[1, 3, 5]查找不存在的 4打印每轮 left、right、mid观察区间长度是否每次都变小。还可以在循环里加一个安全上限防止失控但那是临时的排查手段不是最终修复。6.2 返回错误下标区间语义混乱现象函数没有死循环但返回的下标不是预期值。原因大多是循环退出时没有处理右边界点。左闭右开写法在退出时left right此时left指向的是“第一个大于等于 target 的位置”不一定是 target 本身。修复方法先明确返回语义。如果函数承诺返回“等于 target 的下标”退出后要检查下标合法性并比较nums[left]与 target 是否相等。递归版本同样要注意退出条件。6.3 mid 计算和索引越界现象访问nums[mid]时报 IndexError。原因通常是初始化右边界写成了len(nums)但循环条件用while left right这样第一次就可能访问到nums[len(nums)]。或者是left mid这种更新方式导致 mid 卡在某个位置。修复方法统一区间写法。使用左闭右开时右边界不参与访问循环条件用left right。使用左闭右闭时右边界初始为len(nums) - 1。6.4 排查链路从现象到根因这里给一个固定排查顺序先确认数组到底是不是升序有没有元素无序或类型不一致。确认采用哪套区间写法和循环条件不要左右混用。确认mid计算方式和取整方向。用空数组、单元素、双元素三个用例跑一遍。打印 left、right、mid观察收敛过程。确认返回值语义找不到时返回什么要不要区分“不在数组中”和“插入位置”。如果是递归检查递归深度和初始参数是否正确。如果用了bisect确认自己用的是bisect_left还是bisect_right。这个排查链路适合对照着写排查一次之后再遇到二分查找问题会快很多。7. 工程项目里应该怎么用二分查找7.1 什么场景适合手写二分查找标准有序数组查找直接使用bisect更合适省代码也少出错。手写二分查找的场景包括学习算法、需要自定义比较逻辑比如按对象字段查找、必须返回最小或最大下标而且不想多传参数、或者在面试和比赛中需要现场实现。手写前先想清楚三件事数组是否有序、要查的是什么单个值还是边界、找不到时返回什么。这三件事决定代码怎么写。7.2 封装时先定义清楚返回语义项目里建议封装成专门函数并让语义清晰。比如from bisect import bisect_left def find_insert_position(nums, target): return bisect_left(nums, target) def contains(nums, target): pos bisect_left(nums, target) return pos len(nums) and nums[pos] target调用方不需要知道内部实现只要知道返回值含义。不要在一个函数里混合“返回下标、找不到返回 -1、返回插入位置”多种语义虽然语法上能做但会让调用方很容易用错。学习环境和生产环境的区别也在这里学习时可以打印调试生产环境不要留 debug 输出。学习时可以用递归理解生产环境优先迭代或标准库。学习时一个文件即可生产环境要加函数注释、类型检查和参数校验。生产环境如果数据来自外部还需要考虑空数组、None、元素类型一致性等问题。7.3 可复用的检查清单写二分查找前逐条过一遍数组是否已排序排序方向是升序还是降序。选择左闭右闭还是左闭右开并保持一致。初始 right 是len(nums) - 1还是len(nums)。循环条件是left right还是left right。mid使用left (right - left) // 2。等于目标时是直接返回还是继续收缩。小于目标时 left 移动多少。大于目标时 right 移动多少。循环退出后是否需要再次判断nums[left]是否等于 target。空数组和单元素数组是否安全。返回值语义是否对调用方清晰。7.4 扩展方向二分查找思想不限于数组。找到单调函数的零点、旋转数组中的最小值、在值域上二分答案、在二维有序矩阵中搜索这些题目都可以基于同样的模板演化。建议把左闭右闭和左闭右开各练熟一种然后再学 lower_bound 和 upper_bound 的推导方法最后用bisect模块熟悉生产写法。对初学者来说最有效的练习方式是先不看模板自己写一遍再用边界用例验证写错后对照排查链路找出是哪一步区间收缩出了问题。能够准确说出“为什么返回的是这个下标”之后二分查找有序数组这部分才算真正掌握。