第 9 章搜索 — 无序靠线性,有序靠折半¶

这一章讲什么: 在一个数组里找键。它表面上是「小问题」, 实际把「有没有序」这个条件的价值演到极致:无序时 Ω(n) 没有商量, 有序时一口气从 O(√n) 优化到 O(log n) 再到分布良好时的 O(log log n)。它在全书链条里的位置:Part II(算法)的收官章;Part III 的哈希、BST 都是在回答「能不能比有序数组的 O(log n) 还快(或更通用)」。

1. 顶层全景¶

  无序数组:顺序扫,Ω(n) 铁下界
      └─ 哨兵版:把 key 追加到末尾,循环不用判边界——只省常数,还动数组
  有序数组(区间搜索家族):
      跳跃搜索   大步 √n + 小步 1 → O(√n)  (p 级跳跃 O(p·⁰√n))
      二分搜索   每次砍半 → O(log n)         (正主)
      指数搜索   1,2,4,8… 定位 + 二分收尾 → O(log k),靠前更快
      插值搜索   按值估位置(线性插值) → 均匀时 O(log log n),最坏 O(n)

  图说:横轴是「你对数据知道多少」——无序 < 有序 < 有序且均匀分布,
  每多知道一点,搜索就再快一截。

2. 主线例子:同一数组找 18,三个台阶¶

数组用原书图 9-5 的有序数组(演示值为 [4, 9, 12, 22, 34, 42, 50, 56, 60], 找 18):

第 ① 步线性(无序世界)。 从 0 号起逐个比:4、9、12、22—— 到 22 时若无序只能继续(18 可能在后面);数组无序时平均 n/2 次探测、最坏 n 次¹。

第 ② 步跳跃(有序,第一阶加速)。 跳距 s = ⌊√9⌋ = 3:查位置 3(22>18,停)、回退区间内线性查 12、22——到 22 发现大于 18,判定不在。跳跃次数 n/s + 回退 s,总和 n/s + s,微积分求极值得 s=√n 最优,总探测 2√n²。多级版:跳距先 9(=√n 的平方级),再 3,再 1——p 级时 O(p·⁰√n); 习题 9.3 的妙答:级数趋于无穷时 b→2,「你重新发明了二分搜索」³。

第 ③ 步二分(有序,正主)。 区间 [0, 8],中点 4(值 34>18)→ 缩到 [0, 3]; 中点 1(值 9<18)→ 缩到 [2, 3];中点 2(值 12<18)→ 缩到 [3, 3]; 中点 3(值 22>18)→ 左指针越过右指针,交叉即失败,返回 −1。找 18 不在;找 22 则第一轮中点就命中。每次砍半,O(log n)⁴。

3. 核心原理¶

3.1 无序:线性搜索与哨兵小花招¶

无序数组的搜索下界就是 Ω(n)——不看完都不敢说「不在」。JS 自带的 .includes() / .indexOf() 就是线性搜索,O(n) 从前往后⁷。哨兵版:先把 key 追加到数组尾,循环里不用每轮判断下标越界—— 保证一定命中,命中点在原长之外就是失败。书上泼了冷水:「仍是 O(n), 唯一优势是循环检查更简单;若追加触发 JS 复制数组反而更慢」⁸。

3.2 二分搜索:两种写法一个心思¶

递归版:l > r 即失败;m = (l+r) >> 1(右移一位 = 整除 2, 比 Math.floor((l+r)/2) 更短);中点命中收工,大了搜左半、小了搜右半。迭代版:同样的比较,改成移动 l/r 两个指针——「所有递归都是尾递归, 容易改成循环」⁴。失败的几何意义:l 与 r 交叉——目标值若存在,应夹在已交叉的两者之间, 所以不存在⁵。两个习题级细节:找首个出现位置(命中后记住位置、继续往左缩)与 O(log n) 计数(首位置+末位置相减),都是面试常客⁶。

3.3 指数搜索:目标靠前时的加分项¶

翻倍找界:位置 1、2、4、8… 直到 arr[i] ≥ key,再在该区间内二分。若 key 在位置 k,总代价 O(log k)——越靠前越快, 对「答案常在前面」的数据(如日志查最近事件)比纯二分划算⁹。习题 9.9 的小细节:不必特判 arr[0] === key——循环第一步自然处理¹⁰。

3.4 插值搜索:按「值」猜位置¶

二分总是砍半「不看值」;插值搜索用线性插值估计位置: m = l + (r−l)·(key−arr[l]) / (arr[r]−arr[l])——查词典时找 S 开头的词直接翻到后段,就是这个直觉¹¹。走查(数组 [4,…,60],找 34):首估位置 ≈ 7,值偏小左指针推到 8; 再估 ≈ 10,偏大右指针收到 9;三估命中。两个坑书里明写:端点值相等要防除零;m 可能飞出 [l, r] 区间,先查再比。性能双面:键均匀分布时 O(log log n),分布糟糕(如等比数列)时退化 O(n)—— 「不像二分有保证,是赌数据分布」¹²。

4. 作者的判断与证据¶

「JS 自带方法够用」的实用判断开场即给:无序就 .indexOf(), 自写线性搜索只是为了讲清机制⁷。
跳距 √n 最优给了完整推导(n/s + s 求极值),多级版的 O(p·⁰√n) 与「级数无穷 = 二分」的收敛都点了题——少见的、层层递进的分析链条²。
插值搜索的性能双面明说,没有只讲光环:「最坏 O(n); 均匀分布 O(log log n)(证明不见)」¹²。
测试框架当一等公民(习题 9.1):对数组每个值测「找得到且位置对」, 对 min−3 到 max+3 的每个缺失值测「返回 −1」;作者原话「我用它测出了 bug」¹³。

判断(我们的,不是书里的): 本章最漂亮的不是二分,而是那个「多级跳跃 → 级数取无穷 → 重新发明二分」的收敛论证(习题 9.3)—— 它把一整族算法统一成单个参数(levels)的连续谱。这种「参数化统一」是算法设计里最有迁移价值的思维:遇到新问题时,先问「哪个参数取极限能退化出已知正解」。 如果错,会错在: 习题答案是作者给的解读,物理意义成立, 但「跳跃级数 → 二分」的对应是近似的(i 扮演 l、m 扮演 r−l), 作为直觉极佳,作为严格等价还差一层形式化。

5. 边界与局限¶

只谈数组:哈希表、BST 的搜索留给第 11、12 章——本章的「有序数组」假设在真实系统中常常是奢侈的(数据会变,维护有序有成本)。
插值搜索的非数字键只在脚注级提了一句(转 ASCII/Unicode),没给实现¹²。
二分搜索的溢出坑((l+r) 在 32 位整数下溢出)在 JS 里不存在(双精度), 书里用 >> 移位顺便规避——但没解释为什么别的语言要写成 l + (r-l)/2(补充,不在书里)。
旋转数组查找只在习题里出现,正文没有展开其应用(如「两个有序数组的拼接」场景)。

6. 可带走的¶

无序数组:线性 Ω(n);优先用 JS 自带的 .includes() / .indexOf()。
哨兵只省常数:追加 key 到尾部换「不用判边界」,还动原数组,慎用。
跳跃搜索跳距取 √n 最优(总长 n/s + s 求极值);多级跳跃 O(p·⁰√n)。
二分搜索:中点 (l+r) >> 1;尾递归化循环;l、r 交叉 = 失败。
变体两件套:找首个出现位置(命中后继续往左);O(log n) 计数(首末位置相减)。
指数搜索 O(log k):目标越靠前越快,适合「答案常在前面」的场景。
插值搜索按值猜位置:均匀分布 O(log log n),等比类分布退化 O(n);防除零、防飞出区间。
测试搜索:每个真实值测命中+位置;边界外若干值测 −1(习题 9.1 框架)。

7. 原文地图¶

主题	原书章	原文位置
问题与单次/多次搜索权衡	Search Definition	`text/25-fm-search-definition.txt:32`(搜「single search」)
JS 自带方法与线性	Search Definition	`text/25-fm-search-definition.txt:53`(搜「includes」) · `text/25-fm-search-definition.txt:81`(搜「linearSearch」)
哨兵	Search Definition	`text/25-fm-search-definition.txt:117`(搜「arr[n] = key」) · `text/25-fm-search-definition.txt:128`(搜「even slower」)
跳跃与 √n 最优	Search Definition	`text/25-fm-search-definition.txt:165`(搜「optimum」) · `text/25-fm-search-definition.txt:204`(搜「skip lists」)
多级跳跃	Search Definition	`text/25-fm-search-definition.txt:218`(搜「levels」) · `text/25-fm-search-definition.txt:234`(搜「seriously large」)
二分递归/迭代	Search Definition	`text/25-fm-search-definition.txt:262`(搜「>> 」) · `text/25-fm-search-definition.txt:301`(搜「while (l <= r」)
失败=指针交叉	Search Definition	`text/25-fm-search-definition.txt:294`(搜「crossed」)
指数搜索	Search Definition	`text/25-fm-search-definition.txt:340`(搜「exponentialSearch」) · `text/25-fm-search-definition.txt:351`(搜「O(log k)」)
插值搜索	Search Definition	`text/25-fm-search-definition.txt:361`(搜「interpolate」) · `text/25-fm-search-definition.txt:415`(搜「log log n」)
习题与答案	Chapter 9	`text/72-ch09-chapter-9.txt:47`(搜「rediscovered」) · `text/72-ch09-chapter-9.txt:68`(搜「binaryFindFirst」) · `text/72-ch09-chapter-9.txt:101`(搜「rotationFind」)

出处:「Search Definition」第 45、93 段(text/25-fm-search-definition.txt:45,搜「sequential」;:93,搜「n/2」)。原文:无序只能从头扫;成功搜索平均 n/2 次探测,最坏 O(n)。 ↩
出处:「Search Definition」第 165 段(text/25-fm-search-definition.txt:165,搜「optimum」)。原文:步长 s 时跳跃 n/s 次加回退 s 次,共 n/s+s;「一点微积分证明 s=√n 最优,最多 2√n 次测试」。 ↩↩
出处:「Chapter 9」第 47 段(text/72-ch09-chapter-9.txt:47,搜「rediscovered」)。答案原文:levels 趋于无穷时 b 恒为 2,「你重新发明了二分搜索!大致上 i 取代 l,m 是 l 与 r 之差」。 ↩
出处:「Search Definition」第 258–313 段(text/25-fm-search-definition.txt:259,搜「l > r」;:301,搜「while (l <= r」)。原文:递归版以 l>r 判败;(l + r) >> 1 取中点;「所有递归都是尾递归,容易转成等价迭代」。 ↩↩
出处:「Search Definition」第 294 段(text/25-fm-search-definition.txt:294,搜「crossed」)。原文:失败时 l、r 指针交叉,「缺失值应在 l 左、r 右,故不在数组」。 ↩
出处:「Chapter 9」第 68–92 段(text/72-ch09-chapter-9.txt:68,搜「binaryFindFirst」)。答案原文:命中后 result = m; r = m - 1 继续往左;计数用首末位置差,首搜 −1 则计数 0。 ↩
出处:「Search Definition」第 53–56 段(text/25-fm-search-definition.txt:53,搜「includes」)。原文:.includes() 判存在、.indexOf() 给首位置或 −1;「都是 O(n),从前往后」。 ↩↩
出处:「Search Definition」第 115–128 段(text/25-fm-search-definition.txt:117,搜「arr[n] = key」;:128,搜「even slower」)。原文:末尾追加 key 保证命中,循环免边界检查;「仍 O(n)……若追加导致 JS 建新数组复制,反而更慢」。 ↩
出处:「Search Definition」第 340–351 段(text/25-fm-search-definition.txt:340,搜「exponentialSearch」)。原文:i 从 1 翻倍直到 arr[i] ≥ key,再二分;「若 key 在位置 k,搜索为 O(log k)」。 ↩
出处:「Chapter 9」第 120–130 段(text/72-ch09-chapter-9.txt:120,搜「arr[0]」)。答案原文:不必特判首元素;若 key === arr[0],循环第一步即退出,二分在 [0,1] 内成功。 ↩
出处:「Search Definition」第 364–376 段(text/25-fm-search-definition.txt:361,搜「interpolate」)。原文:l + (r−l)(V−L)/(R−L);查词典直觉开头即给(第 361 段,搜「dictionary」)。 ↩
出处:「Search Definition」第 412–415 段(text/25-fm-search-definition.txt:415,搜「log log n」)。原文:需数值键或可转数值的键;「不像二分每步保证砍半,最坏 O(n)(等比数列分布);均匀分布时可证 O(log log n)(证明不见)」。 ↩↩↩
出处:「Chapter 9」第 10–35 段(text/72-ch09-chapter-9.txt:10,搜「checkSearch」)。答案原文:对 data32 每个值验证命中且位置对;min−3 到 max+3 的缺失值验证返回 −1;题干(第 443 段,搜「some bugs」)说「我用它测我的代码,发现了 bug」。 ↩

第 9 章 搜索 — 无序靠线性,有序靠折半¶