一起动脑筋 · 先看一个小故事
机器人把 16 个候选位置折半，女孩发现只需几次，范围就很小了。
把过程摊开来看
- 16 个候选缩到约 8
- 8 个候选缩到约 4
- 4 个候选缩到约 2
- 2 个候选缩到约 1
每次把候选数量缩小到大约一半，所需轮数增长很慢，这叫对数级增长。
数据翻倍，通常只多一次折半。图画的是候选规模的变化，不是某个具体实现的精确比较记录。
每次为什么能排除一半？
只在从小到大排列的卡片中找 7。灰色卡片表示已经排除。
13579
中间值 5 小于 7；它和左侧都不可能是目标。
×××79
按向下取整的中间下标，比较下标 3 的值 7。
×××7 ✓9
返回下标 3，即第四张卡；9 不必再检查。
01二分查找每次做了什么？
它不是只检查一个元素，更重要的是每次比较后能排除大约一半候选。
n→n/2→n/4→n/8...
021024 个元素需要减半多少次？
1024→512→256→ ... →1
因为：
1024 = 2^10
所以大约需要 10 次减半。
03log₂n 在说什么？
log₂ n 可以理解成：
2 要乘自己多少次，才能到达 n？
也等价于问：n 连续除以 2，大约多少次能缩到 1。
04为什么写 O(log n) 而不是 O(log₂ n)？
因为不同底数的对数只差一个常数倍：
log₂n = 常数 × log₁₀n
大 O 渐近分析会忽略这种固定常数倍，因此通常直接写 O(log n)。
05O(log n) 有多慢增长？
| n | log₂n 约为 |
|---|---|
| 1024 | 10 |
| 1,048,576 | 20 |
| 约 10 亿 | 30 |
输入规模增加很多倍，操作次数只增加一点点。
06只要每次减半就是 O(log n) 吗？
如果每一轮做的额外工作是 O(1)，而问题规模每轮按固定比例缩小，那么常见结果确实是 O(log n)。
如果每一轮内部还做大量工作，总复杂度还要把那部分计算进去。
你已经知道了什么
- 二分查找每轮把候选范围大约减半。
- 从 n 连续减半到 1 需要约 log₂n 轮。
- 因此二分查找是 O(log n)。
- 大 O 中通常省略对数底数。
- O(log n) 增长非常缓慢。
下一篇：怎样让一个很慢的程序变快？
轮到你来试一试
16 个候选变成 32 个，折半轮数大约翻倍吗？
想好了吗？点开看解释
不是，通常只增加一轮：先把 32 缩到约 16，再走原来的过程。