先修：07 计数；08 碰撞；09 对数与比较下界；10 分治与增长率
手里有1024条记录，想按编号找到其中一条。逐项扫描最多看1024条；排好序以后，二分查找最多检查11个位置。看到这里，很容易决定：“先排序，再二分。”
可如果这份临时文件只查一次，排序的钱由谁付？如果每查一次，就插入一批新记录，那份有序状态又由谁维护？
前几章分别算过选择、碰撞、判断和排序。本章把它们放回同一件事：怎样完成一段时间内的全部查找工作。我们要比较的是一份完整账单，先写清单位，再区分哪些成本付一次，哪些会反复发生。
先让比较使用同一种单位
约定每条记录有一个互不相同的整数键；查询要求返回对应记录，或明确回答不存在。键的大小能够一致地比较，记录可按数组下标直接访问。先讨论数据不变的情况。
为避免把不同动作混加，我们统一使用一个三路比较器cmp(a,b)：每调用一次，返回“小于”“等于”或“大于”。本章先把一次调用记作一个比较单位。扫描、排序和二分都用它，扫描虽然只关心是否相等，也按同样的一次调用计费。
二分每检查一个中间键，只调用一次cmp，再根据结果结束或保留一侧。循环条件、下标运算不计入这本比较账。按照每轮去掉中间项、保留至多一半候选的写法，1024个位置最多检查11轮。
第09章数过只有“是、否”两个输出的判断。一轮三路比较可能由不止一次布尔判断实现，不能把“11轮”直接叫作“11次布尔比较”。这里明确换成三路比较器调用数，才能与后面的排序数相加；对数级增长的结论仍然保留。
这也是一个理想化模型：暂时不计读取记录、复制元素、分配空间和缓存访问。它能回答“哪份比较预算较小”，还不能替某台电脑报运行时间。若键是很长的字符串，单次比较还可能检查许多字符，固定单价也需要重新评估。
一次排序，究竟能摊给几次查找
第一种方案保留原顺序，每次从头扫描。查到相等键就停止；没有找到时要检查全部记录。因此，一次查询的比较次数不超过1024；q次查询的预算上界为：
扫描预算＝1024q。
第二种方案先按键建立有序索引。可以把“键、记录位置”复制成一个数组再排序，让原记录保持原样。本节只算这个索引的比较次数，复制和额外空间稍后再补。
沿用第10章的归并算法，n为2的幂时，排序最坏比较次数不超过n log₂n－n＋1。每次归并选择下一项时也调用一次cmp，所以单位一致。代入n＝1024＝2¹⁰，得到：
建索引的排序比较预算＝1024×10－1024＋1＝9217。
建好以后，每次二分查询最多11次比较，q次工作的预算上界为：
排序后二分预算＝9217＋11q。
查询一次时，两份预算分别是1024和9228。查询十次时，则是10240和9327。后者的单次查询虽然便宜，却需要先支付一笔不小的整理成本。
图1：所有条形共用同一尺度。蓝色是查询，橙色是一次排序；图中数字来自模型推算，不是实测耗时。
不必逐个试q。要求第二份预算更小，就解：
9217＋11q＜1024q
9217＜1013q
q＞9217÷1013≈9.099。
由于q是整数，至少要到10次。核对相邻两点：q＝9时，排序后二分为9316，扫描为9216；q＝10时，顺序才反过来。
同样的推法适用于一般预算：设建索引花B，每次索引查询不超过L，扫描不超过S，且S＞L。比较B＋qL与qS，交叉条件就是q＞B÷(S－L)。这说明建索引越贵，需要分摊的查询越多；但这仍只是所选预算模型的交叉条件。
预算交叉，没有许诺每次都更快
现在给结论找一个反例：十次查询的目标，都恰好是原数组第一项。扫描每次只调用一次比较器，总计10次。它根本没有花到10240次。
所以，“第二份最坏上界更小”不能推出“在任何输入上，第二种方案都更省”。上界用来说明最多需要预留多少，不是把每次实际执行都强行填满。上面的q＝10也不是所有程序、所有查询分布通用的回本次数。
另一个边界是起点。如果数据已经按同一键、同一比较规则排好序，并且这个事实可信，当前查找无需再次承担9217次排序比较。只查一次，也可以直接使用至多11次比较的二分。
但如果“已经有序”只是猜测，检查相邻键是否有序本身最多还要1023次比较。可信的格式约定与临时验证，是两种不同起点。不能为了压低账单，把尚未成立的前提当作赠品。
还要确认这些查询能否复用同一份索引。假如接连收到十份互不相关的文件，每份1024条、各查一次，就不能把十次查询合起来，只付一次排序费。按相同模型，十份排序后二分的预算是10×9228＝92280；逐份扫描是10×1024＝10240。可分摊的查询数，应从一次建立结构开始，数到这份结构失效或被丢弃为止。
因此，临时的一次查询、同一份静态数据上的反复查询、接手现成有序数据，虽然都叫“查找”，成本边界并不相同。评估时先说明从哪一步开始算，往往比先挑算法名称更重要。
二分找到了位置，记录还没搬过去
接着放开“数据不变”的约定。一个有序数组保存10、20、30、40、50，现在插入15。二分很快能判断它应放在10与20之间，但那个位置已经有人。
在数组末尾有足够空位的前提下，必须先把50、40、30、20依次右移，再写入15。这里发生4次已有元素搬动和1次新元素写入；找到插入点的比较工作，要另外记。
图2：比较只确定插入位置。为腾出连续位置，四个已有元素仍要各搬一次；图中未计扩容。
对含n项的普通紧凑数组，插到最前面时就要搬动n项。因此，不能从“查位置是对数级”推成“整个插入也是对数级”。Python bisect官方性能说明明确指出，insort的线性插入步骤会主导整体成本。MIT关于有序数组的讲义也把定位与实际搬动分开讨论。
这里说的也是坏情形，不是每次插入都搬n项。若新键已知大于末项，又有剩余空间，可以直接接在末尾；已有元素无需搬动。只修改记录中不参与排序的字段，也未必需要重新排列索引。因此，更新频率还不够，更新的种类和位置同样会改变账单。
比较和搬动不是同一种动作，不能直接把“11次比较＋1024次搬动”写成1035次比较。可以先分别记比较次数C与元素搬动次数M；若确实要折成一个数，再明确每次比较的成本c、每次搬动的成本m，这两部分合计为cC＋mM。c与m需要来自选定模型或测量，不能默认为相等；新元素写入、分配等费用继续另列。
把时间范围内的工作全部列出，总账就变成：
总成本＝建索引成本＋各次查询成本之和＋各次更新维护成本之和。
每一项都必须按同一套计价方式展开。建索引里的复制、归并中的搬动，不能因为发生得早就漏记；数组扩容可能引入额外复制。空间则可以另列占用，不必硬折成时间。
频繁更新还关系到正确性：新增记录若没有进入索引，二分可能报告不存在；键改变却没有重新归位，也会破坏有序前提。究竟每次及时维护，还是攒一批再重建，要同时看维护成本与查询允许读到多旧的数据。后者若要求即时正确，就不能静默使用过期索引。
换成分桶，也要把桶里面算进去
第08章给过另一条路：按散列值分桶，再核对原始键。它不要求先把所有键排成一条大小序列，但也没有保证每个桶都很短。
继续使用h(x)＝x mod 4。若键是1、5、9、13、17，五个对象都进1号桶。查询21时也进入该桶，却一个都不相等。在本章采用的链表桶里，要依次核对五个键，才能报告不存在。
图3：分桶后的查找成本，仍包含桶内核对。此图只示范逐项检查的链表桶，不代表所有散列表实现。
将键扩展为1、5、9，直到4n－3，仍然全部同桶；查询不存在的4n＋1，就需n次原键核对。这给出了一个明确的失效边界：有桶号可算，不等于候选已经有效缩小。MIT的散列讲义同样讨论了长链导致的退化。
此时还应算散列计算、桶的空间与更新。至于某种规则下通常有多长的链，需要说明键或散列规则怎样选择，之后才能使用概率工具；本章不凭“分了桶”就许诺平均常数时间。
它也没有违反第09章的比较下界。只允许通过比较区分键的模型，与允许计算桶号并按下标取位置的模型，提供的操作不同。若键本来就是一小段整数，甚至可以直接用键作下标，但需要为约定范围准备位置。比较下界不能不带前提地禁止散列或直接寻址；额外操作及其空间代价也要如实计入。
回到那份1024条记录
现在可以更具体地选：只查一次的临时无序数据，先看扫描是否已够用；已可信有序的数据，直接二分；静态数据要反复查，比较建索引与后续查询的合计预算；更新频繁，则把保持索引有效的工作一起算进去。选择分桶时，再检查原键核对、坏分布与空间要求。
还应对齐返回结果：本章只问某个键是否存在及其记录。如果要求输出某一范围内的全部记录，找到起点以后仍要访问并输出那些结果。把一个只返回位置的操作，与一个返回大量内容的操作直接比耗时，即使计时单位相同，也没有比较同一份工作。
第07章让我们数清可能的状态，第08章提醒有限编号会丢失区别，第09章追问一次判断能区分什么，第10章把排序的各层工作加回来。本章最后保留的习惯，是检查有没有漏账：前提如何取得，结构如何建立，变化以后如何继续成立。
一个方法真正省下的工作，应该在完整范围里仍然省下。比较预算可以帮助筛选方案；到了实际系统，还要把读取、复制、缓存与输入特点带回去验证。数学给我们的，是一份能够追问和核对的理由。
顺手试一下
题目1：查询多少次，预算才交叉
有256个互异整数键，数据静态且原先无序。仍用本章三路比较器计数：归并排序最多256×8－256＋1＝1793次，二分每次最多9次，扫描每次最多256次。先排序后二分的预算，至少在第几次查询时严格小于扫描？能否据此保证那次工作实际更快？
**提示：**列出1793＋9q＜256q，再检查相邻整数。想想目标在原数组什么位置。
**参考答案：**不等式等价于q＞1793÷247≈7.259，故至少8次。q＝7时，两份预算为1856与1792；q＝8时为1865与2048。不能保证实际更快：若每次查询都命中原数组首项，扫描八次只需8次比较；其他运行成本也未计入。
题目2：少记了哪两笔成本
一个程序按h(x)＝x mod 4分桶，用链表保存键1、5、9、13。它声称：“查询17只需一次算余数。”另一个程序要向有序数组10、20、30、40插入5，声称：“二分找到位置，插入就完成了。”两句话各漏了什么？假定数组有空位，具体数出搬动与新写入次数。
**提示：**桶号确认身份了吗？插入点原先是否为空？
**参考答案：**17进入1号桶后，还需核对4个原键，全部不等才回答不存在；一次散列计算不能代替核对。插入5前，需要依次将40、30、20、10右移，共4次已有元素搬动，再写入5一次，定位的比较另计。比较、散列计算、搬动的单价未约定时，应分别列账，不能统称为同一种比较。
来源与延伸阅读
- Python bisect官方文档：插入点查找与实际插入的区别，以及性能注意事项
- MIT 6.006，2011年秋，第5讲，第2页：有序数组的定位与移动成本
- MIT 6.006，2020年春，第4讲，第1—3页：比较模型、直接寻址，以及链表桶的坏分布
作者：Jiancheng Wang · 数学之美（独立原创）