之前做一次内部代码评审功能很简单从一个已经排好序的整数列表里判断某个数字是否存在存在就返回下标。新同事写得很直接if target in arr: return arr.index(target)这段代码没有问题测试用例也全过了。但等我把列表长度调到一千万、查询次数调到一万次以后它就像被按住了慢放键十几秒都出不来结果。问题不在 Python 本身也不在这位同事的编码习惯而在于我们默认了一个不该成立的假设数组是有序的但我们仍然在用线性扫描的方式处理它。这篇文章想聊的就是 Python 里处理有序数组最基础也最容易翻车的一个技巧——二分查找。我一直觉得二分查找真正解决的不是“找一个数”这件小事而是“在一个具有单调性质的空间里快速定位目标”这一整类问题。看懂这一点比背十个二分模板都重要。1. 为什么有序这个条件经常被代码浪费掉1.1 大多数人默认的写法复杂度是 O(n)很多人在拿到“有序数组查找”这个需求时第一反应不是写二分而是用 Python 自带的in、index()或者for循环。arr [1, 3, 5, 7, 9, 11] target 7 if target in arr: # 内部是线性扫描 print(arr.index(target))这样的写法在数据量小的时候完全够用。5 个元素、50 个元素、500 个元素线性查找的耗时几乎可以忽略不计。但问题在于当数据量变大、查询次数变多O(n) 的成本就会成倍放大。线性查找的本质是即使你知道数组已经排好序了你仍然从第一个元素开始逐个比对直到找到目标或者遍历完整个数组。它没有利用“有序”这个信息而是把这个信息当成了普通列表。1.2 复杂度差异的体感到底有多大很多人对 O(log n) 和 O(n) 的差异没有体感这里可以做一个很简单的估算。假设一个列表有 10 万个有序元素线性查找最坏情况下要比较 10 万次。二分查找最多比较约 17 次。如果只是查一次10 万次也比较不了多少毫秒。但如果要查 1 万次线性查找就是最多 10 亿次比较而二分查找是 17 万次比较。这个差距在真实接口服务里会直接表现为几毫秒和几十秒甚至分钟级的区别。所以我在代码评审里经常说一句话不要看单次执行多快要看在重复调用下的累积成本。一次接口查一次我们很难感知但如果这个函数被循环调用、被多个请求触发O(n) 的浪费就会被放大到肉眼可见。1.3 问题的本质信息没有被利用“数组是有序的”这句话不是一句可以忽略的描述它是一个非常强的约束条件。有序意味着对于任意i j一定有arr[i] arr[j]。这句话给了我们一个单调性的保证。既然单调那么当我比较arr[mid]和target的时候我不仅能知道当前位置是否相等还能知道目标应该在左半边还是右半边。二分查找做的就是利用这个单调性在每一轮比较之后直接丢掉一半数据。这是它和线性查找最本质的区别。2. 二分查找的核心机制折半搜索不是表面动作而是空间收缩2.1 一个干净的标准实现先给一个最常用的迭代版本。这个版本我建议所有 Python 开发者都能默写出来def binary_search(nums: list[int], target: int) - int: 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]。取中点mid。如果中点正好等于目标直接返回。如果中点小于目标说明目标只可能在中点右边于是把左边界挪到mid 1如果中点大于目标说明目标只可能在中点左边于是把右边界挪到mid - 1。每一步搜索空间都会缩小一半。只有当left right时说明区间已经被压缩完目标不存在返回-1。2.2 循环条件和边界为什么是重点很多人在初学二分时最苦恼的是“我到底该写left right还是left right”。这不能靠背只能靠理解。上面这个版本用的是闭区间[left, right]。闭区间的意思是left和right都可能是目标位置。所以循环条件必须是while left right否则当区间缩到只剩一个元素时这个元素就永远不会被检查。当nums[mid] target时mid本身已经确定不是答案所以新的左边界应该是mid 1而不是mid。同理当nums[mid] target时新的右边界应该是mid - 1。这里最容易犯的错是写成left mid right mid这样在只剩两个元素的时候可能会陷入死循环因为左右边界一直没有真正收缩。理解“当前mid已经被排除”这一点边界的写法就不容易错了。如果你采用另一种写法比如左闭右开区间[left, right)那么循环条件和边界更新都会不一样。这点后面讲lower_bound时会再提到。2.3 从“找到等于 target 的数”到“找到第一个满足条件的位置”标准二分的写法解决的是“找等于 target 的某个位置”。但实际工程里有个更高频的需求有序数组里可能有很多个 target我想找到第一个或最后一个 target 的位置。又或者数组里根本没有 target但我想找到第一个大于 target 的元素用来做插入点。这类问题不能靠标准二分加一个往前线性寻找的循环来解决。因为最坏情况下如果数组全是同一个数字往前找第一个 target 的位置会退化成 O(n)。正确的做法是改变二分里的判断条件不是比较“等不等于 target”而是比较“满不满足某个条件”。3. 处理重复元素工程里绕不开的 left_bound / right_bound3.1 普通二分在重复元素下不够用假设数组是arr [1, 2, 2, 2, 3, 4, 5] target 2用前面的标准二分可能返回下标 2也可能返回下标 1 或 3。具体返回哪个取决于mid的取值和数组长度的奇偶性。如果你只想知道“是否存在”这没问题。但如果你想知道“第一个 2 在哪个位置”标准二分就不够了。更关键的是当你做范围统计、区间删除、插入排序时你需要的不是任意一个位置而是边界位置。3.2 lower_bound 和 upper_bound 的写法Python 内置的bisect模块已经提供了现成实现import bisect arr [1, 2, 2, 2, 3, 4, 5] left bisect.bisect_left(arr, 2) right bisect.bisect_right(arr, 2) print(left) # 1 print(right) # 4bisect_left返回第一个大于等于target的位置。bisect_right返回第一个大于target的位置。所以说bisect_left和bisect_right的差值就是重复元素的数量。如果不想依赖库也可以自己实现一套理解边界逻辑的版本。下面这个是我个人比较推荐的写法用的是左闭右开区间[left, right)def lower_bound(nums: list[int], target: int) - int: left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid return left def upper_bound(nums: list[int], target: int) - int: left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid return left注意看这两段代码的差异lower_bound在nums[mid] target时收缩左边界upper_bound则在nums[mid] target时收缩左边界。这个的差别决定了返回的位置是“第一个等于”还是“第一个大于”。用左闭右开区间时循环条件是left right因为当left right时区间已经为空。而更新right时直接取mid因为右边界本身是开区间不包含在当前搜索范围里。这套写法和闭区间写法不是一回事不建议混着用。3.3 返回值到底是索引、插入点还是布尔值实现二分查找之前你最好先把返回值语义定清楚。这是工程里很容易翻车的地方。常见的三种语义找到返回下标找不到返回-1。返回第一个大于等于 target 的位置也就是插入点。只返回是否存在的布尔值。同一个二分函数如果一会儿返回下标一会儿返回插入点调用方就会写出非常难维护的代码。我的建议是函数名和文档字符串要明确定义语义不要写一个含糊的search()。你可以在函数名上直接体现比如find_index、find_first_ge、contains。这看起来只是个命名问题但实际影响很大。一个语义不清晰的二分函数在代码评审里几乎必然会被质疑因为你没法说清楚边界情况到底怎么处理。4. 二分查找的适用边界哪些场景该用哪些场景别硬上4.1 适用场景二分查找不是银弹。它适合的场景主要有三类数据是有序的或者是可排序的。如果数组无序你需要先花 O(n log n) 排序那就要考虑排序成本是否划算。查询次数较多。如果只查一次线性查找有时候反而更简单因为不需要维护有序状态。数据支持随机访问。也就是说你能以 O(1) 的时间拿到任意下标的值。Python 的 list 满足这个条件。一个典型场景是已经排序好的配置列表、区间列表、白名单或者一次排序后反复查询的数据。在这种情况下二分查找能把单次查询从 O(n) 降到 O(log n)。4.2 不适用场景如果你遇到以下情况不要硬上二分数据是链表。链表不能随机访问取mid要 O(n)二分不仅没有优势反而比线性查找更慢。数据频繁插入、删除。为了保持有序每次变动都可能涉及 O(n) 的数据搬移。如果查询次数不高直接线性查找或采用其他数据结构更合理。数据量很小。比如两位数长度的数组线性查找本身开销极低二分的前置逻辑反而显得复杂。数据不能一次性载入内存。比如超大文件、远端数据库。这种情况你需要的是 B 树、B 树这类索引结构或者数据库本身就支持高效范围查询。4.3 选型判断框架我一般会按这个顺序去判断一个查找需求该不该用二分数据会不会频繁变化如果是先考虑用平衡树、跳表或其他有序容器。数据量会不会很大如果只有几百条线性查找足够。查询是否是热点路径如果每秒钟要查很多次二分值得写。数据能否排序如果排序成本能接受且会复用那二分是一个好选择。是否需要对边界做复杂判定比如范围查询、最近值查询这时考虑bisect而不是自定义二分。把这一步想清楚比直接写代码更重要。5. 从一道题到一种通用思维二分不只是在数组里找数5.1 常见升级寻找插入位置有序数组里最经典的一个变体是给定一个数字返回它应该插入的位置让插入后数组仍然有序。如果数组里有重复值bisect_left会返回重复区间的开头bisect_right会返回重复区间的末尾。这个插入位置其实就是我们在某些排序算法里常用的“稳定插入”概念。arr [1, 3, 5, 6] target 5 pos bisect.bisect_left(arr, target) print(pos) # 2arr[:pos]里的元素都小于 targetarr[pos:]里的元素都大于等于 target。这个性质可以帮我们快速定位数据的位置而不必关心目标是否存在。5.2 把“二分”抽象为“单调判定”一旦你理解了二分查找的本质是“利用单调性收缩搜索空间”你会发现它能解决的问题远不止在数组里找一个数。很多算法题里有这样一种模式答案存在一个取值范围内并且答案本身满足单调性。也就是说当我把答案从大到小或从小到大排列时一定存在一个分界点分界点一侧满足条件另一侧不满足。这时候我就可以对“答案”做二分查找。比如“在给定体积下所有货物能否在 D 天内运完”这类问题判断一个体积是否满足条件只需要线性扫描但我们要找的是最小满足条件的体积。这个最小体积就可以用二分去逼近。这种思路在工程里也成立比如调参时找一个临界值、日志分析里找一个时间边界、限流里找一个阈值。它的核心不是“折半”而是“空间可收缩”。5.3 一套可复用的练习路径如果你想把二分查找真正练熟我建议不要只刷一道题就停。可以按这个顺序来写标准二分在有序无重复数组中找目标值。写lower_bound找第一个大于等于 target 的元素。写upper_bound找第一个大于 target 的元素。用上面两个边界函数解决“统计 target 出现次数”的问题。练一道变体比如在旋转有序数组中查找最小值。完成这五步后你对二分边界条件的理解会比刷十道重复题目更扎实。尤其是第 2、3 步它们会强迫你思考循环不变量和边界收缩方向。6. 写二分查找最容易遇到的五个坑和自测方法6.1 五个典型坑第一个坑循环条件写错。闭区间写左闭右开区间写。混用会导致漏查或死循环。第二个坑mid计算方式。Python 里(left right) // 2通常不存在溢出问题因为整数不限长度。但在其他语言里left right可能溢出所以很多教材会建议写left (right - left) // 2。Python 里你可以更关注逻辑但建议理解这个写法的用意。第三个坑边界更新时没有排除mid。如果nums[mid] target说明 mid 不可能是答案别再把left设为mid而是设为mid 1。否则可能死循环。第四个坑对空数组和单元素数组没有直觉。写完后一定先用空数组、单元素数组、双元素数组测一遍。第五个坑返回语义没有定义清楚。同一个函数里一会儿返回下标一会儿返回-1一会儿返回插入位置。这样调用方很难判断结果。6.2 用随机数据做基准验证写二分时我几乎每次都会用一个随机化测试脚本来验证逻辑。思路很简单生成一个随机有序数组随机生成 target再用线性查找的结果作为基准和二分的结果对比。import random def binary_search(nums: list[int], target: int) - int: 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 for _ in range(10000): arr sorted(random.sample(range(-1000, 1000), 200)) target random.randint(-1000, 1000) expected -1 for i, x in enumerate(arr): if x target: expected i break actual binary_search(arr, target) if actual ! expected: print(出错, target, expected, actual, arr) break else: print(全部通过)这个测试有个小缺点如果数组里有重复 target线性查找找到的不一定是二分返回的那个位置。所以随机生成时可以用random.sample生成无重复数字或者把判断条件改成“只要返回的是 target 且下标合法即可”。对于自己写的二分先用无重复数据验证基础逻辑再单独测重复数据是比较稳的做法。6.3 从单次跑通到批量查询很多人在学习二分时只写了函数没有真正放到工程场景里验证。我建议你在本地做一个更真实的测试生成一个百万级有序数组重复查询几千次统计耗时。这样你才能建立起“O(log n) 到底比 O(n) 快多少”的体感。更进一步如果你的业务确实需要反复查询有序数组可以考虑把数据加载到内存后用bisect。它本身就是 C 实现的比纯 Python 手写循环更快语义也更清晰。绝大多数情况下工程里优先用内置模块自定义二分更多是用在那些需要定制“条件判断”的场景里。最后说一句二分查找听起来很简单真正写好却需要理解边界条件、循环不变量和返回值语义。它的价值不在于让你背出一个模板而在于让你意识到数据结构里的单调性质是可以被用来大幅压缩搜索空间的信息。如果你今天只记住一件事我建议是下次在有序数组里查找时先别急着写for i in range(len(arr))先想一想这个数据被排序之后的优势你有没有真正用到。先从最小的例子开始写一个标准二分再写一个lower_bound用随机数组自测几轮。等你对边界条件有了直觉二分查找就会从“背模板”变成“很自然的工具”。