企业官网建设流程全解析

之前做一次内部代码评审，功能很简单：从一个已经排好序的整数列表里判断某个数字是否存在，存在就返回下标。新同事写得很直接：

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

这段代码的逻辑拆开看，只有四步：

1. 确定搜索区间为[left, right]。
2. 取中点mid。
3. 如果中点正好等于目标，直接返回。
4. 如果中点小于目标，说明目标只可能在中点右边，于是把左边界挪到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_bound

3.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) # 4

• bisect_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. 找到返回下标，找不到返回-1。
2. 返回第一个大于等于 target 的位置，也就是插入点。
3. 只返回是否存在的布尔值。

同一个二分函数，如果一会儿返回下标，一会儿返回插入点，调用方就会写出非常难维护的代码。我的建议是：函数名和文档字符串要明确定义语义，不要写一个含糊的search()。你可以在函数名上直接体现，比如find_index、find_first_ge、contains。

这看起来只是个命名问题，但实际影响很大。一个语义不清晰的二分函数，在代码评审里几乎必然会被质疑，因为你没法说清楚边界情况到底怎么处理。

4. 二分查找的适用边界：哪些场景该用，哪些场景别硬上

4.1 适用场景

二分查找不是银弹。它适合的场景主要有三类：

1. 数据是有序的，或者是可排序的。如果数组无序，你需要先花 O(n log n) 排序，那就要考虑排序成本是否划算。
2. 查询次数较多。如果只查一次，线性查找有时候反而更简单，因为不需要维护有序状态。
3. 数据支持随机访问。也就是说，你能以 O(1) 的时间拿到任意下标的值。Python 的 list 满足这个条件。

一个典型场景是：已经排序好的配置列表、区间列表、白名单，或者一次排序后反复查询的数据。在这种情况下，二分查找能把单次查询从 O(n) 降到 O(log n)。

4.2 不适用场景

如果你遇到以下情况，不要硬上二分：

• 数据是链表。链表不能随机访问，取mid要 O(n)，二分不仅没有优势，反而比线性查找更慢。
• 数据频繁插入、删除。为了保持有序，每次变动都可能涉及 O(n) 的数据搬移。如果查询次数不高，直接线性查找或采用其他数据结构更合理。
• 数据量很小。比如两位数长度的数组，线性查找本身开销极低，二分的前置逻辑反而显得复杂。
• 数据不能一次性载入内存。比如超大文件、远端数据库。这种情况你需要的是 B 树、B+ 树这类索引结构，或者数据库本身就支持高效范围查询。

4.3 选型判断框架

我一般会按这个顺序去判断一个查找需求该不该用二分：

1. 数据会不会频繁变化？如果是，先考虑用平衡树、跳表或其他有序容器。
2. 数据量会不会很大？如果只有几百条，线性查找足够。
3. 查询是否是热点路径？如果每秒钟要查很多次，二分值得写。
4. 数据能否排序？如果排序成本能接受且会复用，那二分是一个好选择。
5. 是否需要对边界做复杂判定？比如范围查询、最近值查询，这时考虑bisect而不是自定义二分。

把这一步想清楚，比直接写代码更重要。

5. 从一道题到一种通用思维：二分不只是在数组里找数

5.1 常见升级：寻找插入位置

有序数组里最经典的一个变体是：给定一个数字，返回它应该插入的位置，让插入后数组仍然有序。

如果数组里有重复值，bisect_left会返回重复区间的开头，bisect_right会返回重复区间的末尾。这个插入位置，其实就是我们在某些排序算法里常用的“稳定插入”概念。

arr = [1, 3, 5, 6] target = 5 pos = bisect.bisect_left(arr, target) print(pos) # 2

arr[:pos]里的元素都小于 target，arr[pos:]里的元素都大于等于 target。这个性质可以帮我们快速定位数据的位置，而不必关心目标是否存在。

5.2 把“二分”抽象为“单调判定”

一旦你理解了二分查找的本质是“利用单调性收缩搜索空间”，你会发现它能解决的问题远不止在数组里找一个数。

很多算法题里有这样一种模式：答案存在一个取值范围内，并且答案本身满足单调性。也就是说，当我把答案从大到小或从小到大排列时，一定存在一个分界点，分界点一侧满足条件，另一侧不满足。这时候，我就可以对“答案”做二分查找。

比如“在给定体积下，所有货物能否在 D 天内运完”这类问题，判断一个体积是否满足条件只需要线性扫描，但我们要找的是最小满足条件的体积。这个最小体积就可以用二分去逼近。

这种思路在工程里也成立：比如调参时找一个临界值、日志分析里找一个时间边界、限流里找一个阈值。它的核心不是“折半”，而是“空间可收缩”。

5.3 一套可复用的练习路径

如果你想把二分查找真正练熟，我建议不要只刷一道题就停。可以按这个顺序来：

1. 写标准二分：在有序无重复数组中找目标值。
2. 写lower_bound：找第一个大于等于 target 的元素。
3. 写upper_bound：找第一个大于 target 的元素。
4. 用上面两个边界函数解决“统计 target 出现次数”的问题。
5. 练一道变体，比如在旋转有序数组中查找最小值。

完成这五步后，你对二分边界条件的理解会比刷十道重复题目更扎实。尤其是第 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，用随机数组自测几轮。等你对边界条件有了直觉，二分查找就会从“背模板”变成“很自然的工具”。