二分查找 · 数据结构与算法
怎么在 20 步之内查完一百万个有序元素？
课程目录为什么需要它
在 1 到 1,000,000 之间猜数，每次只告诉你「大了/小了」，只要每次都猜中间，最多 20 次就能猜中。这个想法就是二分查找，数据库索引、git bisect 和无数面试题背后都是它。
直觉理解
维护一个答案一定在其中的区间 [lo, hi]。看中间那个：
- 相等 → 找到了
- 中间的太小 → 答案在右边：
lo = mid + 1 - 太大 → 在左边：
hi = mid - 1
每一步都把区间砍掉一半，所以大约需要 log₂ n 步：一百万要 20 步，十亿要 30 步。列表必须有序。
定义
二分查找
Searching a sorted range by comparing with the middle and discarding half each time. O(log n).在有序区间里查找：每次和中间比较，扔掉一半。O(log n)。
不变式
A fact that stays true on every loop step, here: "if the target exists, it is between lo and hi". Writing it down prevents off-by-one bugs.每一轮循环都保持成立的事实，这里是：「如果目标存在，它一定在 lo 和 hi 之间」。把它写下来能避免差一错误。
示例
一步一步做二分查找
动手试试打印每次的区间，看它怎么缩小。
def search(xs, target):
lo, hi = 0, len(xs) - 1
while lo <= hi:
mid = (lo + hi) // 2
print("look at", mid, xs[mid])
if xs[mid] == target:
return mid
if xs[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 23))逐步执行
- L40..9 的中间是 4：值是 16。
- L916 < 23，所以答案在 4 的右边。
- L11区间 5..9，中间 7 是 56：太大了。
- L14区间 5..6，中间 5 是 23。看了 3 次就找到了。
5
常见错误
while lo < hi 配上 hi = mid - 1
把不同模板的循环条件和更新方式混在一起，会漏掉最后一个候选。选定一个模板，心里记着不变式。
输入没有排序
在无序列表上，二分查找会悄悄给出错误答案，不报任何错。先排序，否则别用它。
小测验
1. 在 1,000,000 个有序元素里二分查找，大约需要多少步？
查看答案
答案：A
2²⁰ ≈ 1,000,000，所以砍 20 次一半。
2. 这段代码会输出什么？
import bisect
scores = [55, 61, 70, 70, 84, 92]
print(bisect.bisect_left(scores, 70), bisect.bisect_right(scores, 70))查看答案
答案：A
bisect_left：70 能插入的最左位置（2）。bisect_right：最后一个 70 之后（4）。
动手练习
3 道练习，分三层：先预测程序的输出，再按新需求改程序，最后从零写一个。代码在浏览器里运行，提交马上判题。
- 预测输出数一数看了几次
准确写出这段程序的输出。
- 改需求修好停不下来的查找
当目标比中间值大时，这个二分查找会无限循环。修好更新方式，让区间总是在缩小。
- 从零写第一个坏版本
发布了版本 1…n；从某个版本开始，之后的每个版本都是坏的。
is_bad(v)告诉你版本 v 是不是坏的。写函数first_bad(n, is_bad)，用二分查找返回第一个坏版本（测试会数你调用的次数）。假设版本 n 是坏的。
本课术语
| 术语 | 中文 | 英文定义 |
|---|---|---|
| Binary search | 二分查找 | Halving a sorted range at each step to find a target in O(log n). |
| Invariant | 不变式 | A fact that stays true on every step of a loop. |