搜索算法
假设面前有一行数字卡片，我们想找写着 11 的卡片。搜索要回答：有没有匹配的卡片？如果有，它出现在哪个位置？逐张检查是一种办法。但如果卡片已经排好顺序，这个顺序能不能告诉我们，哪些位置一定不可能是 11 呢？
01线性搜索：明确已经排除了什么
目标值就是要找的数。位置说明卡片放在哪里，与卡片数值不同。画面中的位置从 1 编号；许多编程语言从 0 编号，这改变的是标签，不是搜索的道理。先检查第一张：匹配就停止，不匹配就排除这个位置，继续下一张。
每一步开始前，前面的卡片已经检查过，而且都不匹配；还没检查的卡片仍有可能。每次比较失败后，这句话仍然成立。所以走到末尾仍未匹配，就确实没有目标。这就是“未找到”的理由，而不是觉得找得够久就停下。
还没有检查卡片。边框范围包括目标仍可能出现的所有位置。
把排列改成“打乱”再试一次。方法仍然成立，因为它没有假定顺序。把目标改成 10，可以观察不存在的值；然后把排列改回“从小到大”，再把目标改成 2。这时它在首位，可以看到匹配只需一次比较。如果有多个匹配，当前从左到右的方法会返回第一个。
02二分搜索：先说明为什么可以排除一半
现在让卡片从小到大排列：每张都不大于下一张。假设中间卡片是 9，目标是 11。这个 9 左边的数都至多是 9，所以不可能是 11。我们可以一次排除中间及其左边。如果中间大于目标，同样的道理让我们排除中间及其右边。
我们只保留仍可能匹配的范围，下一步检查这个范围的中间，而不是原来整行的中间。如果有两个中间位置，这里取靠左的一个。比较不匹配时，检查过的中间位置也会被排除，所以范围一定变小。范围为空就说明目标不存在。匹配时立刻停止；有重复值时，这不一定是第一个匹配的位置。
还没有检查卡片。边框范围包括目标仍可能出现的所有位置。
试着选“打乱”。实验不会继续使用整段排除规则，因为我们已经不知道左边是否都较小。例如打乱后，中间的 7 不能告诉我们 2 在哪一侧。允许排除一半的根据是顺序本身，仅仅挑一个中间位置还不够。
03为什么工作量的增长不同
线性搜索有 张卡片时，末位匹配或目标不存在都需要 次比较。卡片数翻倍，这种最坏情况的工作量也翻倍。目标恰好在首位时，最好情况仍只需一次。它们描述不同输入，并不矛盾。
对二分搜索，反过来数：限定比较次数，最多能区分多少个位置？零次比较只处理空列表。一次可以检查一个中间位置。两次时，第一次的中间占一个位置，两侧还能各检查一个，得到 。三次时，每侧可以有三个，得到 。
用 表示 次比较的容量，就有 、。它的规律是 ：零次时成立；把前一次的结果代入，得到 ，所以每个下一步也成立。要覆盖 个位置，选满足 的最小整数 。这个容量说明少于这些次数不可能总是够用。接下来还要检查：每次选中间，确实能做到这个上界吗？
假设 ，并且 。检查中间这张，如果不匹配，就把它排除。若 是奇数，两侧各有 张；若 是偶数，较大的一侧有 张。由于 是奇数，不超过它的偶数 至多是 。因此无论哪种情况，每侧都至多有 张。比较失败后，留下的一侧就放得进剩余 次比较的容量。重复这个道理，直到比较次数用完，此时范围必定已经为空；遇到匹配则可以提前结束。这说明上界也确实足够。八张卡片时，三次不能保证够用，四次则一定足够。
二分搜索还假设可以直接到达中间位置，数组这种按编号存储的一排位置就能支持它。如果为了到达中间必须沿着许多链接逐个走过去，数值比较少并不保证总工作量少。数据无序时，先排序也需要工作。只找一次，逐项检查可能更合适；要在不变的数据上反复查找，先付出一次排序工作则可能有用。
看看排序怎样建立所需的顺序04使用规则，并说明规则允许什么
查看推理
第一个中间是第 4 位的 9。第 1–4 位全部小于 14，因此排除第 1–4 位。剩下第 5–8 位，靠左的中间是第 6 位，值为 14。两次比较就找到。
查看推理
我们刚检查过，它不是目标。保留它不会增加任何真实可能，却可能在只剩一个位置时让范围不再缩小。排除它既保留全部真实可能，也保证继续推进。
查看推理
五次容量是 ，所以可以处理 31 张。32 张时，某些目标或不存在的目标需要第六次，因为五层只有 31 个中间位置可以检查。
