反过来用它 — 一路砍半,以及「只数 0 有几个」的对数

这一章讲三件事: 「每判断一次砍掉一半」为什么这么值钱; 它要付什么前提(这一条最容易被忽略); 以及那个把大数变小的工具——对数——到底是什么。

它在全书链条里的位置: 第 13 章说「每多一样条件就翻一倍」是灾难。 这一章把同一件事掉个头:每处理一步,剩下的就少一半。 灾难变成了利器,而这是全书唯一一次「拿指数爆炸赚钱」。 需要的基础: 第 13 章的翻倍;会做除法。

1. 先看现象:15 个人里,问 3 次就能找出犯人

15 个嫌疑人站成一排,其中只有 1 个是犯人。 你可以问其中任何一个人「犯人在哪里」,他会答三种话之一¹:

• 「我就是犯人。」
• 「犯人在我左边。」
• 「犯人在我右边。」

只问 3 次,能找出犯人吗?能。

先把规模缩小看 3 个人(又是第 11 章那个动作): 向中间那个人问一次,三种回答正好对应三个人——一次就锁定了²。

15 个人的办法是同一个:每次都向「还剩下的那一段」正中间的人提问³。 这一节只是现象层,真正要走的走查在下一节——因为程序里查的不是人,是数据。

2. 主走查:15 个排好序的数里找 67

这一节是全章的主走查,每一步都写出当前范围和被看的那个数⁴。

  15 个数,已经从小到大排好:
  16  17  23  29  31  42  45  58  62  66  67  71  78  83  88
                              ↑
                        正中间是 58

  要找的目标:67

第 1 次判断:看正中间的 58。 67 比 58 大 → 左边那半连同 58 一起排除, 剩下右边 7 个:62 66 67 71 78 83 88。

  62  66  67  71  78  83  88
              ↑
        正中间是 71

第 2 次判断:看正中间的 71。 67 比 71 小 → 右边那半连同 71 一起排除, 剩下左边 3 个:62 66 67。

  62  66  67
      ↑
  正中间是 66

第 3 次判断:看正中间的 66。 67 比 66 大 → 左边那半连同 66 一起排除, 剩下 1 个。

判断了 3 次,范围从 15 缩到 1,剩下的那一个就是 67。 主走查走完了。

  范围:15 → 7 → 3 → 1
  被看的数: 58   71   66      ← 注意:被看的那三个数里没有 67

  图说:「判断了 3 次」和「第 4 个位置上是答案」是两件事。
       三次判断的作用是把范围砍到只剩一个;
       剩下的那一个必定是目标,因为题目保证目标就在这堆数里。

原书对这道题的说法是:和找犯人完全一样,仅通过 3 次判断就找到了 67⁵。 这种「总是判断当前范围正中间那个数」的查法,叫二分法查找⁶。

3. 为什么是 3 次:每判断一次砍掉一半

这一节回答:15 和 3 之间是什么关系。

关键只有一句:向正中间提问一次,就能筛掉一多半⁷。

这里面藏着第 11 章那种结构:第 n 次判断能覆盖的人数, 等于「左边那一半」加「本人」加「右边那一半」⁸:

  P(0) = 1                          ← 不问,只能在 1 个人里确定
  P(n) = P(n−1) + 1 + P(n−1)        ← 问一次:左边、本人、右边

  P(0) = 1
  P(1) = 1 + 1 + 1 = 3
  P(2) = 3 + 1 + 3 = 7
  P(3) = 7 + 1 + 7 = 15             ← 3 次判断,15 个,对上了

这条递推式和第 11 章汉诺塔的一模一样,只有起点不同(汉诺塔是 H(0) = 0)⁹。 解析式是 P(n) = 2ⁿ⁺¹ − 1¹⁰。

4. 于是好消息来了:30 次覆盖 21 亿

这一节把上面那条关系推到大规模。

15 个数,顺着一个个找也不费事。但二分法查找的威力在大量数据上¹¹:

判断次数	能在多少个数据里找到目标
10 次	2047 个
20 次	209 万 7151 个
30 次	21 亿 4748 万 3647 个

看这三行的跨度:判断次数只从 10 涨到 30(三倍), 覆盖的数据却从两千涨到 21 亿(一百万倍)。

换个说法更好记:多判断一次,能查的数据就翻一倍¹²。

这正是第 13 章那个指数爆炸,只不过站在了你这一边: 上一章是「条件每多一个,工作量翻一倍」,这一章是「工作量每多一次,能力翻一倍」。

5. 这条性质出门会撞见的两个名字

这一节的内容不在原书里,但你出门一定会撞见,所以我们补上。

补充(不在书里):「数据变多之后,一段程序会慢多少」—— 这一类性质有个统称,叫复杂度(用来衡量开销随着数据规模涨得多快)¹³。

只看时间的那一种,叫时间复杂度;而二分法查找这种「数据翻一倍、只多花一次判断」 的算法,在代码和面试里写作 O(log n)¹⁴。

这两个名字要记住,但更要记住它们是我们补的: 原书从头到尾没有用过「时间复杂度」这个词,也没有出现过大 O 记号—— 这是作者「尽量不用算式」那条方针的一部分(第 18 章第 6 节会把这笔账逐条列出来)。

6. 前提:必须先排好序

这一节是这一章最容易被跳过、而代价最大的一节。

二分法查找不是白捡的,它有一个硬前提:数据必须按大小排好¹⁵。

理由很直接:如果数据是乱的,你看了正中间那个 58, 根本无法判断 67 在它左边还是右边——那三种回答就不成立了¹⁶。

  排好序:  16 17 23 29 31 42 45 [58] 62 66 67 71 78 83 88
           └─ 都比 58 小 ─┘         └─ 都比 58 大 ─┘   ← 一次判断能砍掉一半

  没排序:  67 16 83 42 31 88 23 [58] 45 17 78 29 62 71 66
           └── 大小混在一起 ──┘      └── 大小混在一起 ──┘  ← 一次判断什么也砍不掉

所以「排好序」这件事本身就是价值。 原书在讲问题空间那一节说过类似的话: 「从头开始按顺序查找」不难,难的是如何达到「可以从头顺序查找」这个状态¹⁷。

7. 换个方向:与其扛着大数,不如数它有几个 0

从这一节起换一件工具,而它和上面那件是一体两面。

求 100 000 里 0 的个数(5),这件事就叫求 100 000 的对数¹⁸。

数	它的对数
100	2
1000	3
100 000	5
10 000 000 000 000 000	16

再庞大的数,它的对数都是个小数目¹⁹。 原书给的量感对照很漂亮:宇宙中所有基本粒子的总数是一个后面跟着 80 个 0 的数, 而它的对数只有 80²⁰。

严格说来,「1000 的对数是 3」应该说成「以 10 为底,1000 的对数是 3」—— 这里的「底」就是「什么的 3 次方等于 1000」里的那个「什么」²¹。

8. 对数和乘方,是一件事的两头

这一节把上一节那个定义接到你已经会的东西上。

下面这两句话说的是同一件事²²:

  10 的 5 次方是 100 000        写成:10⁵ = 100 000
  以 10 为底,100 000 的对数是 5   写成:log₁₀ 100 000 = 5

  图说:乘方是「反复乘到指定次数」,对数是「乘多少次能得到这个数」。
       一个从次数问结果,一个从结果问次数 —— 互为逆运算。

换成 2 也一样:2 的 3 次方是 8,所以以 2 为底 8 的对数是 3; 256 是 2 的 8 次方,所以以 2 为底 256 的对数是 8²³。

回头看第 2 节那道题,现在可以一句话说清了: 15 个数要判断 3 次、21 亿个数要判断 30 次——判断次数就是数据个数的对数(以 2 为底)。

9. 对数最早的用处:把乘法降成加法

这一节另起一处走查,交代对数当初为什么被发明出来。

第 01 章讲过指数法则:10ᵃ × 10ᵇ = 10ᵃ⁺ᵇ。 拿它来算 100 × 1000²⁴:

  100 × 1000
      ↓ 取对数(数 0 的个数)
    2   +   3
      ↓ 加起来
        5
      ↓ 还原(算 10 的 5 次方)
     100 000

  图说:整条路上没有做过一次乘法 —— 乘法被换成了一次加法。
       代价是要来回换两次(取对数、再还原)。

这就是对数最初的用处:把复杂的乘法计算换成简单的加法²⁵。

但这里有个躲不掉的疑问,原书让学生替读者问了出来: 加法是比乘法简单,可算对数不是比乘法更难吗? 老师的回答是:可以事先把对数做成表²⁶。

对数是约翰·奈皮尔在 1614 年发现的²⁷。 当时的天文学家没有计算机,却要处理庞大的数值、做大量乘法, 所以奈皮尔的对数表和计算尺被广泛使用²⁸。

计算尺就是把这件事做成了一把尺:两根刻度相同的尺子错开摆好, 读一下刻度就完成了加法;而把刻度改成按对数排(每往右一格数值乘 10), 同一个动作就变成了乘法²⁹。

10. 顺带一件实用的:把爆炸压成一条斜线

这一节收个尾,把第 13 章那张吓人的图治好。

第 13 章那条折纸曲线前面贴地、后面垂直,根本没法看。 但如果把竖轴改成对数刻度(1、1024、1048576…… 等间距排), 那条爆炸的曲线就变成了一条老实的斜线³⁰。

这就是对数图表³¹。它的用处是:让指数爆炸的数据变得能看、能比。 你在监控面板上看到的「对数坐标」按钮,治的正是同一件事。

11. 作者的判断、我们的判断,以及这一章的边界

说法	书里给了什么
3 次判断找出 67	给了完整走查(15 → 7 → 3 → 1)+ 一张四行的图
判断 30 次覆盖 21 亿	给了三个数,并给了脚注说明:判断 n 次能覆盖 2ⁿ⁺¹ − 1 个
必须排好序	给了理由:否则判断不了在左边还是右边
对数是「数 0 的个数」	给了定义 + 量感对照(宇宙粒子总数的对数只有 80)
对数把乘法降成加法	给了完整走查 + 历史(奈皮尔、天文学家、计算尺)
时间复杂度 / O(log n)	原书完全没有——这两个名字是我们补的

判断(我们的,不是书里的):这一章的真正价值,是让你在动手之前问一句 「我能不能先把它排好序」。 二分法查找本身几乎不用你写(每种语言的标准库里都有), 但「先花一次排序的代价,换来之后每次查找都砍半」这笔账,是要你自己算的。 查一次不划算,查一百万次就非常划算。 如果错,会错在: 如果数据一直在变(边写边查),维护有序本身的代价可能反而更高 ——那时改用「按内容直接算出存放位置」的办法更合适。判据是:写的次数和查的次数,哪个多。

这一章的边界:

• 没有讲二分法查找的实现细节(边界怎么取、有没有重复元素、 怎么避免中点计算溢出)——这些是实际写代码时最容易出错的地方;
• 没有讲怎么排序;排序本身的代价原书一个字没提;
• 对数只讲了以 10 和以 2 为底,没有讲自然对数;
• 计算尺那两节严重依赖图,转码后的文本里只剩下刻度的描述;
• 「时间复杂度」和「O(log n)」是我们补的,原书刻意避开了这套记号。

12. 可带走的

1. 每判断一次砍掉一半:15 个数里找 67,看 58 → 看 71 → 看 66,三次判断范围就剩 1 个;
2. 被判断的数和最后剩下的数是两件事——那三次看的是 58、71、66,而答案是 67;
3. 判断 n 次能覆盖 2ⁿ⁺¹ − 1 个数据;10 次 2047 个,20 次 209 万,30 次 21 亿;
4. 多判断一次,能查的数据就翻一倍——这是第 13 章那个爆炸站在了你这一边;
5. 前提是数据必须排好序,否则「在左边还是右边」根本判不了;
6. 「排好序」本身就是价值:难的不是顺序查找,是达到「可以顺序查找」的状态;
7. 对数就是「数一数 0 有几个」:100 000 的对数是 5;再大的数,对数都很小;
8. 对数和乘方互为逆运算:一个从次数问结果,一个从结果问次数;
9. 对数能把乘法降成加法(100 × 1000 → 2 + 3 → 还原成 100 000), 奈皮尔 1614 年发现它,天文学家靠它和计算尺干活;
10. 把竖轴换成对数刻度,爆炸的曲线就被压成一条斜线;
11. 出门会撞见的两个名字:时间复杂度、O(log n)——但要记得它们不是这本书教的。

13. 原文地图

主题	原书章	原文位置
15 人找犯人	第7章　指数爆炸	text/12-ch07.txt:201(搜「有 15 个犯罪嫌疑人」) · :220(搜「仅通过 3 次问话」) · :229(搜「只要向中间的那个人提问」)
15 个数里找 67	第7章　指数爆炸	text/12-ch07.txt:333(搜「下图中有 15 个数按顺序排列」) · :336(搜「16 17 23 29 31 42 45 58 62 66 67 71 78 83 88」) · :345(搜「也仅通过 3 次判断就找到了 67」)
二分法查找的定义	第7章　指数爆炸	text/12-ch07.txt:331(搜「二分法查找（binary search）」) · :359(搜「每判断 1 次就能筛选出近一半的查找对象」)
递推公式与解析式	第7章　指数爆炸	text/12-ch07.txt:289(搜「就能筛选掉超过一半的人」) · :302(搜「P(0) = 1」) · :320(搜「这个递推公式和「汉诺塔」的递推公式形式相同」) · :323(搜「P(n) = 2n+1 − 1」)
10 次 / 20 次 / 30 次	第7章　指数爆炸	text/12-ch07.txt:357(搜「2047」) · :358(搜「21 亿 4748 万 3647」) · :362(搜「多判断 1 次就能从」)
必须排好序	第7章　指数爆炸	text/12-ch07.txt:359(搜「因此，必须将查」) · :703(搜「如果书架中的书陈列有序」)
对数是什么	第7章　指数爆炸	text/12-ch07.txt:373(搜「就称作求 100 000 的对数」) · :377(搜「例如，宇宙」) · :380(搜「以 10 为底」)
对数与乘方互逆	第7章　指数爆炸	text/12-ch07.txt:385(搜「对数和乘方是互逆关系」) · :445(搜「log2 8 = 3」) · :463(搜「所以 log2 256 = 8」)
用加法做乘法、奈皮尔、计算尺	第7章　指数爆炸	text/12-ch07.txt:527(搜「乘法比加法难」) · :560(搜「对数是由约翰·奈皮尔」) · :565(搜「计算尺就是使用对数进行乘法计算时的一种辅助工具」)
对数图表	第7章　指数爆炸	text/12-ch07.txt:480(搜「即使发生指数爆炸也能绘制出一目了然的图表来」) · :486(搜「对数图表能够帮助我们把握发生指数爆炸的数急速增长的情况」)

Footnotes

1. 出处:「第7章　指数爆炸——如何解决复杂问题」第 201 段(text/12-ch07.txt:201,搜「有 15 个犯罪嫌疑人」)与第 208 段(text/12-ch07.txt:208,搜「我是犯人」)。原书列了三种回答,并说明其中有 1 个是正确的。 ↩

2. 出处:「第7章　指数爆炸——如何解决复杂问题」第 229 段(text/12-ch07.txt:229,搜「只要向中间的那个人提问」)。原文特意点明:中间的人不一定必须就是犯人,即使不直接向犯人提问,也可根据他的回答确定谁是犯人。 ↩

3. 出处:「第7章　指数爆炸——如何解决复杂问题」第 251 段(text/12-ch07.txt:251,搜「在包含犯人的范围内，向正中间的人提问」)与第 254 段(text/12-ch07.txt:254,搜「【第 1 次提问】」)起的三段。 ↩

4. 出处:「第7章　指数爆炸——如何解决复杂问题」第 333 段(text/12-ch07.txt:333,搜「下图中有 15 个数按顺序排列」)与第 336 段(text/12-ch07.txt:336,搜「16 17 23 29 31 42 45 58 62 66 67 71 78 83 88」)。原书第 338 段起列了三种判断结果:等于 67(找到)、大于 67(在左边)、小于 67(在右边),并注明这三种兼顾完整性和排他性。 ↩

5. 出处:「第7章　指数爆炸——如何解决复杂问题」第 345 段(text/12-ch07.txt:345,搜「也仅通过 3 次判断就找到了 67」)。原书这里只画了四行示意图(第 347 到 353 段),没有写出每一次被判断的是哪个数——上面那三个数(58、71、66)是我们照它的规则一步步走出来的。 ↩

6. 出处:「第7章　指数爆炸——如何解决复杂问题」第 331 段(text/12-ch07.txt:331,搜「二分法查找（binary search）」)。原书说它也叫「二分法」「二分查找」。 ↩

7. 出处:「第7章　指数爆炸——如何解决复杂问题」第 289 段(text/12-ch07.txt:289,搜「就能筛选掉超过一半的人」)。 ↩

8. 出处:「第7章　指数爆炸——如何解决复杂问题」第 308 段(text/12-ch07.txt:308,搜「能整理出以下递推公式」)与第 316 段(text/12-ch07.txt:316,搜「P(n)」)。原书把式子的三段各自标了注:回答「在左边」之后能确定的最大人数、本次提问的对象、回答「在右边」之后能确定的最大人数。 ↩

9. 出处:「第7章　指数爆炸——如何解决复杂问题」第 320 段(text/12-ch07.txt:320,搜「这个递推公式和「汉诺塔」的递推公式形式相同」)。原文明说「不过 n = 0 时的值不同」。 ↩

10. 出处:「第7章　指数爆炸——如何解决复杂问题」第 323 段(text/12-ch07.txt:323,搜「P(n) = 2n+1 − 1」)。 ↩

11. 出处:「第7章　指数爆炸——如何解决复杂问题」第 355 段(text/12-ch07.txt:355,搜「15 个数不算多」)与第 357 段(text/12-ch07.txt:357,搜「2047」)、第 358 段(text/12-ch07.txt:358,搜「21 亿 4748 万 3647」)。原书在这里挂了一条脚注:和「找犯人」相同,判断 n 次就能从 2ⁿ⁺¹ − 1 个数据中找出目标。 ↩

12. 出处:「第7章　指数爆炸——如何解决复杂问题」第 362 段(text/12-ch07.txt:362,搜「多判断 1 次就能从」)。原文的原话是:多判断 1 次就能从近 2 倍的查找对象中找出目标数据;二分法查找有效地利用了指数爆炸。 ↩

13. 补充(不在书里):这一段的名字与说法取自 Wikipedia「Time complexity」条目,原句是「the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm」。来源:https://en.wikipedia.org/wiki/Time_complexity(查阅于 2026-08-25)。原书全书没有出现过「时间复杂度」这个词。 ↩

14. 补充(不在书里):二分法查找的这条性质,标准说法是「Binary search runs in logarithmic time in the worst case, making O(log n) comparisons, where n is the number of elements in the array」;同一条目还写明最坏情况下要做 ⌊log₂(n) + 1⌋ 次比较循环。来源:Wikipedia「Binary search」 https://en.wikipedia.org/wiki/Binary_search(查阅于 2026-08-25)。我们保留这两个名字,是因为读者出门在代码、面试、文档里一定会撞见它们;但它们不是原书教的。 ↩

15. 出处:「第7章　指数爆炸——如何解决复杂问题」第 359 段(text/12-ch07.txt:359,搜「因此，必须将查」)。 ↩

16. 出处:「第7章　指数爆炸——如何解决复杂问题」第 360 段(text/12-ch07.txt:360,搜「找对象“有序”排列」)。原文顺带回扣了找犯人那道题:排成一排的人都知道犯人在自己的左边还是右边。 ↩

17. 出处:「第7章　指数爆炸——如何解决复杂问题」第 703 段(text/12-ch07.txt:703,搜「如果书架中的书陈列有序」)。原文的原话是:「从头开始按顺序查找」不难,困难的是如何达到「从头开始顺序查找」这一状态。 ↩

18. 出处:「第7章　指数爆炸——如何解决复杂问题」第 373 段(text/12-ch07.txt:373,搜「就称作求 100 000 的对数」)。原文还说,也称作取对数、计算对数。 ↩

19. 出处:「第7章　指数爆炸——如何解决复杂问题」第 376 段(text/12-ch07.txt:376,搜「再庞大的数，其对数也会相对较小」)。 ↩

20. 出处:「第7章　指数爆炸——如何解决复杂问题」第 376 段(text/12-ch07.txt:376,搜「例如，宇宙」)。原书把那个数完整印了出来,并说它的对数只有 80。 ↩

21. 出处:「第7章　指数爆炸——如何解决复杂问题」第 380 段(text/12-ch07.txt:380,搜「以 10 为底」)。原文说「底」也称为「基数」——和第 01 章讲按位计数法时那个「基数」是同一个词。 ↩

22. 出处:「第7章　指数爆炸——如何解决复杂问题」第 385 段(text/12-ch07.txt:385,搜「对数和乘方是互逆关系」)与第 407 段(text/12-ch07.txt:407,搜「log 是 logarithm 的缩」)。 ↩

23. 出处:「第7章　指数爆炸——如何解决复杂问题」第 445 段(text/12-ch07.txt:445,搜「log2 8 = 3」)与第 463 段(text/12-ch07.txt:463,搜「所以 log2 256 = 8」)。 ↩

24. 出处:「第7章　指数爆炸——如何解决复杂问题」第 501 段(text/12-ch07.txt:501,搜「现假设 100 和 1000 进行「乘法计算」」)与第 506 段(text/12-ch07.txt:506,搜「但是只要做指数 2 和指数 3 的」)。 ↩

25. 出处:「第7章　指数爆炸——如何解决复杂问题」第 527 段(text/12-ch07.txt:527,搜「乘法比加法难」)。原文把整件事归纳成三步:分别取对数、把对数相加、再做一次乘方还原。 ↩

26. 出处:「第7章　指数爆炸——如何解决复杂问题」第 551 段(text/12-ch07.txt:551,搜「虽然加法比乘法简单」)与第 553 段(text/12-ch07.txt:553,搜「不过可以将对数事先做成表」)。这是原书的师生对话,学生问的正是读者会问的那句。 ↩

27. 出处:「第7章　指数爆炸——如何解决复杂问题」第 560 段(text/12-ch07.txt:560,搜「对数是由约翰·奈皮尔」)。原书给的生卒年是 1550—1617,发现年份是 1614 年。 ↩

28. 出处:「第7章　指数爆炸——如何解决复杂问题」第 562 段(text/12-ch07.txt:562,搜「当时的天文学家」)。 ↩

29. 出处:「第7章　指数爆炸——如何解决复杂问题」第 565 段(text/12-ch07.txt:565,搜「计算尺就是使用对数进行乘法计算时的一种辅助工具」)与第 586 段(text/12-ch07.txt:586,搜「若数轴的刻度保持等间隔不变」)。原书用三张图分别演示了 3 + 4 = 7、10³ × 10⁴ = 10⁷、3 × 4 = 12。 ↩

30. 出处:「第7章　指数爆炸——如何解决复杂问题」第 482 段(text/12-ch07.txt:482,搜「用普通图表表示纸对折后的厚度时」)与第 484 段(text/12-ch07.txt:484,搜「请看对数图表纵轴上的数」)。 ↩

31. 出处:「第7章　指数爆炸——如何解决复杂问题」第 480 段(text/12-ch07.txt:480,搜「即使发生指数爆炸也能绘制出一目了然的图表来」)与第 486 段(text/12-ch07.txt:486,搜「对数图表能够帮助我们把握发生指数爆炸的数急速增长的情况」)。「监控面板上的对数坐标按钮」是我们加的例子,不在书里。 ↩