3. 有序数组中的查找¶

3.1. 分析¶

对于会被反复查找的大型记录集合，顺序查找慢得让人无法接受。减少查找时间的一种方法是对记录进行预处理，即把它们排序。给定一个有序数组，对简单、从左到右的线性查找的明显改进，是检查 L 中的当前元素是否大于 $K$。如果是，那么我们就知道 $K$ 不可能出现在数组中靠后的位置，可以提前结束查找。但这仍然不会改善算法的最坏情况代价。

在任何计算机科学课程中，学生最早学习的算法之一就是如何更快地查找有序线性表。但让我们试着忘记已知的东西，用全新的眼光来看待这个问题。我们还要考虑典型模型假设中的一些细节，这些假设或许能引出比我们自以为"最佳"的算法更好的（平均情况）算法。

3.1.1. 跳查找¶

我们还可以观察到，如果在有序数组 L 中先看位置 1，发现 K 更大，那么我们连位置 0 也一并排除了。因为更多往往更好，那如果我们看 L 中的位置 2，并发现 $K$ 还是更大呢？这样就只用一次比较排除了位置 0、1 和 2。如果我们把这一点推向极端，先看 L 中最后一个位置，却发现 $K$ 更大，又会怎样？那我们就在一次比较中知道 $K$ 不在 L 中。知道这一点是有用的，但"我们应该总是从最后一个位置开始看"这一结论又错在哪里？问题在于，虽然有时我们会了解到很多信息（一次比较中我们可能得知 $K$ 不在线性表中），但通常我们只能了解到一点点信息（最后一个元素不是 $K$）。

于是问题就变成了：应当跳多大才合适？这引出一个被称为跳查找的算法。对某个值 $j$，我们检查 L 中每隔 $j$ 个的元素，也就是说，检查 $\mathbf{L}[j]$、$\mathbf{L}[2j]$ 等等。只要 $K$ 大于我们正在检查的值，就继续向前。但当我们在 L 中遇到一个大于 $K$ 的值时，就在长度为 $j-1$ 的一段上做线性查找，我们知道如果 $K$ 在线性表中，就一定被夹在这个范围内。

如果我们定义 $m$ 使得 $mj \leq n < (m+1)j$，那么这个算法的总代价至多是 $m + j - 1$ 次三向比较。（它们之所以是三向的，是因为在每次把 $K$ 与某个 $\mathbf{L}[i]$ 比较时，我们都需要知道 $K$ 是小于、等于还是大于 $\mathbf{L}[i]$。）因此，在 $n$ 个元素上以大小为 $j$ 的跳跃运行该算法的代价为

\[\mathbf{T}(n, j) = m + j - 1 = \left\lfloor \frac{n}{j} \right\rfloor + j - 1.\]

$j$ 取什么值最好？我们希望使代价最小：

\[\min_{1 \leq j \leq n} \left\{\left\lfloor\frac{n}{j}\right\rfloor + j - 1\right\}\]

求导数并解 $f'(j) = 0$ 求出最小值，即 $j = \sqrt{n}$。在这种情况下，最坏情况代价约为 $2\sqrt{n}$。

这个例子体现了算法设计的一条基本原则：我们希望在选取子线性表所花的工作与查找子线性表所花的工作之间取得平衡。一般来说，让各子问题的工作量大致相当是一个好策略。这就是一个分治算法的例子。这似乎是两层算法（把线性表拆分成大小相等的子线性表，然后再处理这些子线性表）能做到的最好程度。但算法设计的另一条原则是增加层数。

如果我们将这个想法扩展到三级？我们首先会以某种大小的跳跃（ $j$ ）来找到一个大小为 $j-1$ 的子列表，其末尾值为 $K$ 。然后，我们通过以某种较小的大小（例如 $j_1$ ）的跳跃来处理这个子列表。最后，一旦我们找到一个大小为 $j_1 - 1$ 的括号子列表，我们将进行顺序搜索来完成这个过程。

先做两层跳跃、再做顺序查找，这听起来可能很绕。做两层算法（也就是跳查找先通过跳跃找到一个子线性表，再在子线性表上做顺序查找）或许是有意义的，但做三层算法几乎从来都说不上有意义。相反，当需要超过两层时，我们几乎总是通过递归来推广。这正引导我们走向有序数组最常用的查找算法——二分查找。

3.1.2. 二分查找¶

你大概已经相当熟悉二分查找了。为了有一个具体的实现可以讨论，这里给出一个实现。

Settings

Saving...

Server Error
Resubmit

你当然知道，在有序线性表上做二分查找远比顺序查找要好。为什么会这样？因为我们掌握了线性表无序时没有的额外信息可用。你大概早就"知道"标准二分查找算法的最坏情况代价是 $O(\log n)$。让我们实际算一算，确认它确实在 $O(\log n)$ 之内，也看看如何应付精确刻画递归算法行为的那些棘手的建模细节。之后，我们再证明二分查找对于求解有序线性表上的查找问题确实是最优的（至少在最坏情况下）。

如果我们愿意对分析粗略一些，就可以这样推理：我们查看一个元素（代价为 1），然后在数组的一半上重复这个过程。这样会得到一个形如 $f(n) = 1 + f(n/2)$ 的递推关系。但如果我们想更精确一些，就需要仔细想想最坏情况下到底发生了什么。首先，我们应当注意到，我们所做的不只是把数组切成两半。我们绝不会再次查看已经测试过的某个位置。例如，如果输入规模是九，那么我们实际上会查看位置 4（因为 $(9-0)/2 = 4$ 向下取整），然后要么继续考虑左边的四个位置（位置 0 到 3），要么考虑右边的四个位置（位置 5 到 8）。但如果共有十个元素呢？那么我们实际上会查看位置 5（因为 $(10-0)/2 = 5$）。接下来，我们要么需要继续处理左边的五个位置（位置 0 到 4），要么处理右边的四个位置。这意味着在最坏情况下，当数组规模为奇数时，我们查看的略少于一半；当数组规模为偶数时，正好查看一半。为了刻画这一点，我们可以使用下取整函数，得到如下精确的最坏情况模型：

\[\begin{split}f(n) = \left\{ \begin{array}{ll} 1 & n=1\\ f(\lfloor n/2 \rfloor) + 1 & n > 1 \end{array} \right.\end{split}\]

由于 $n/2 \geq \lfloor n/2 \rfloor$，并且我们假设 $f(n)$ 是非降的（因为增加更多元素不会减少工作量），所以我们可以用简化式 $f(n) = f(n/2) + 1$ 来估计上界。

这个递推关系通过展开很容易求解：

\[\begin{split}\begin{eqnarray*} f(n) &=& f(n/2) + 1\\ &=& \{f(n/4) + 1\} + 1\\ &=& \{\{f(n/8) + 1\} + 1\} + 1 \end{eqnarray*}\end{split}\]

然后化简为

\[f(n) = f(n/2^i) + i = f(1) + \log n = \log n + 1\]

现在，我们可以用归纳法证明这是正确的。

根据归纳假设，$f(n/2) = \log(n/2) + 1$。

\[\begin{split}\begin{eqnarray*} f(n/2) + 1 &=& (\log(n/2) + 1) + 1\\ &=& (\log n - 1 + 1) + 1\\ &=& \log n + 1 = f(n). \end{eqnarray*}\end{split}\]

二分查找的平均代价如何计算？这需要一些建模，因为我们需要知道各种输入的概率。我们将基于如下假设来估计：

$X$ 在 L 中。
$X$ 出现在任意位置的概率相同。
对某个非负整数 $k$，有 $n = 2^k - 1$。

代价是多少？

用一次探查命中的机会有一种。
用两次探查命中的机会有两种。
用 $i$ 次探查命中的机会有 $2^{i-1}$ 种。
$i \leq k$。

由此得到的等式是什么？

\[\frac{1\times 1 + 2\times 2 + 3 \times 4 + ... + \log n 2^{\log n-1}}{n} = \frac{1}{n}\sum_{i=1}^{\log n}i 2^{i-1}\]

注意 $2^{\log n-1} = n/2$。

为了求解这个求和式：

\[\begin{split}\begin{eqnarray*} \sum_{i=1}^k i2^{i-1} &=& \sum_{i=0}^{k-1}(i+1)2^i = \sum_{i=0}^{k-1} i 2^i + \sum_{i=0}^{k-1} 2^i\\ &=& 2 \sum_{i=0}^{k-1} i 2^{i-1} + 2^k - 1\\ &=& 2 \sum_{i=1}^{k} i 2^{i-1} - k 2^k + 2^k - 1 \end{eqnarray*}\end{split}\]

注意在上面的等式中，我们做了变量代换：$i \rightarrow i+1$。

接下来怎么办？从原式中减去！

\[\sum_{i=1}^{k} i 2^{i-1} = k 2^k - 2^k + 1 = (k - 1)2^k + 1.\]

注意

\[\sum_{i=1}^k i 2^{i-1} = 2 \sum_{i=1}^k i 2^{i-1} - k 2^k + 2^k -1\]

于是，

\[\begin{split}\begin{eqnarray*} \sum_{i=1}^k i 2^{i-1} &=& k2^k - 2^k +1\\ &=& (k-1)2^k +1 \end{eqnarray*}\end{split}\]

现在我们回到原式的求解。既然手里已经有该求和式的闭式解，就可以做适当的变量代换，重新表述原式。

\[\begin{split}\begin{eqnarray*} \frac{1}{n}\sum_{i=1}^{\log n}i 2^{i-1} &=& \frac{(\log n - 1)2^{\log n} + 1}{n}\\ &=& \frac{n (\log n -1) + 1}{n}\\ &\approx& \log n - 1 \end{eqnarray*}\end{split}\]

所以平均代价只比最坏情况代价少大约一两次比较。

如果我们放宽 $n = 2^k - 1$ 的假设，得到的精确代价为：

\[\begin{split}f(n) = \left\{ \begin{array}{ll} 0 & n=0\\ 1 & n=1\\ \frac{\lceil \frac{n}{2} \rceil - 1}{n}f(\lceil \frac{n}{2} \rceil - 1) + \frac{1}{n} 0\ + \\ \frac{\lfloor \frac{n}{2} \rfloor}{n}f(\lfloor \frac{n}{2} \rfloor) + 1& n > 1 \end{array} \right.\end{split}\]

这个等式的各组成部分对应的含义如下：

左侧：$X < L[i]$
$L(i) == X$ 没有额外的代价，其概率为 $1/n$
右侧：$X > L[i]$

3.1.3. 下界证明¶

所以，二分查找 $O(\log n)$ 的时间看起来相当不错。我们能做得比这更好吗？用与证明排序下界类似的证明方法，可以证明对于有序线性表上的查找，这是最坏情况下的最优算法。

我们用决策树来为算法建模。与查找无序线性表不同， L 中元素之间的比较不会告诉我们关于它们相对顺序的新信息（因为 L 已经有序），所以我们只考虑 $K$ 与 L 中某个元素的比较。当我们从决策树的根结点开始运行算法时，当前的知识不会排除 L 中的任何位置，所以所有位置都是潜在候选。当我们根据 $K$ 与 L 中某个元素的比较结果在决策树中选取分支时，会逐渐排除潜在候选。最终我们到达树中的一个叶结点，它代表 L 中唯一可能包含 $K$ 的位置。树中至少要有 $n+1$ 个结点，因为 $K$ 可能处于 $n+1$ 个互不相同的位置（ L 中的任意位置，外加根本不在 L 中的情况）。树中必有某条路径的深度至少为 $\log n$ 层，而树中最深的结点代表该算法的最坏情况。因此，任何在有序数组上运行的算法，最坏情况下都至少需要 $\Omega(\log n)$ 次比较。

我们可以修改这个证明，来求平均代价的下界。同样，我们用决策树为算法建模。只不过现在我们关心的不是最深结点的深度（最坏情况），因而不是最深结点深度最小的那棵树。相反，我们想知道叶结点的"平均深度"的最小可能值是多少。把总路径长度定义为每个结点的层数之和。某个结果的代价就是对应结点的层数加 1。算法的平均代价就是各结果代价的平均值（总路径长度 / $n$）。平均深度最小的树是什么样的？这与二分查找所对应的树是一样的。因此，二分查找在平均情况下也是最优的。

虽然在有序数组中查找时，二分查找确实是有序线性表最坏情况与平均情况下的最优算法，但仍有许多情形可能促使我们改选其他算法。换句话说，还有其他一些模型值得考虑。一种可能是，我们掌握了数组中数据分布的一些信息。如果 L 中每个位置包含 $K$ 的可能性相等（等价地，数据在整个键范围内分布得很均匀），那么插值查找在平均情况下达到 $\Theta(\log \log n)$。如果数据没有排序，那么使用二分查找就需要预先付出排序的代价，这只有在线性表上会进行多次—至少 $O(\log n)$ 次—查找时才值得去做。二分查找还要求线性表（即使已经排序）用数组或其他能以相同代价随机访问所有元素的结构来实现。最后，如果我们事先知道所有的查找请求，那么在最极端的查找分布下，我们或许更愿意按频率对线性表排序后再做线性查找，或者使用自组织线性表。

3.1.4. 插值查找与二次二分查找¶

如果我们对键值的分布一无所知，那么刚才已经证明，二分查找是对有序数组可用的查找算法中的最佳选择。然而，有时我们的确掌握一些关于键值期望分布的信息。（或者，至少我们自以为知道，并针对这一键分布来设计。）考虑一个人在大型词典中查词时的典型行为。大多数人当然不会使用顺序查找！但他们也不会真正使用二分查找，至少在接近要找的词之前不会。改进之处在于，查找一般不从词典的中间开始。查找以 'S' 开头的词的人通常会假设，以 'S' 开头的词条大约位于整本词典四分之三处。因此，他们会先把词典翻到约四分之三处，再根据看到的内容决定下一步在哪里查找。换句话说，人们通常会利用关于键值期望分布的一些知识来"计算"下一步该在哪里查找。这种"计算式"二分查找称为字典查找或插值查找。在字典查找中，我们按照与 $K$ 的值相适应的方式来查找 L 中的位置 $p$，具体如下。

\[p = \frac{K - \mathbf{L}[1]}{\mathbf{L}[n] - \mathbf{L}[1]}\]

这个等式把 $K$ 的位置计算为最小键值与最大键值之间距离的一个比例。接下来，这会被转换为数组中同一比例所在的位置，并首先检查这个位置。与二分查找一样，找到的键的值会排除该位置上方或下方的所有记录。然后可用实际找到的键值，在数组剩余范围内计算一个新位置。下一次检查就基于这个新的计算进行。这一过程持续进行，直到要么找到想要的记录，要么数组被不断缩小直到没有记录为止。

字典查找的一种变体称为二次二分查找（QBS），我们将对它进行详细分析，因为它的分析比一般字典查找要容易。 QBS 首先计算 $p$，然后检查 $\mathbf{L}[\lceil pn\rceil]$。如果 $K < \mathbf{L}[\lceil pn\rceil]$，那么 QBS 将按照大小为 $\sqrt{n}$ 的步长依次向左探查，也就是说，我们依次访问

\[\mathbf{L}[\lceil pn - i\sqrt{n}\rceil], i = 1, 2, 3, ...\]

直到到达一个小于或等于 $K$ 的值。类似地，对于 $K > \mathbf{L}[\lceil pn\rceil]$，我们以 $\sqrt{n}$ 为步长向右移动，直到在 L 中遇到一个大于 $K$ 的值。此时我们距离 $K$ 已不超过 $\sqrt{n}$ 个位置。（暂且）假设只要常数次比较就能把 $K$ 夹定在一个大小为 $\sqrt{n}$ 的子线性表内。然后我们取出这个子线性表，递归地重复这一过程。也就是说，在下一层，我们计算一个插值点，从子数组中的某个位置开始。然后我们（视情况）以大小为 $\sqrt{\sqrt{n}}$ 的步长向左或向右移动。

QBS 的代价是多少？注意 $\sqrt{c^n} =c^{n/2}$，我们将反复对当前子线性表的大小取平方根，直到找到要找的元素。因为 $n = 2^{\log n}$，而 $\log n$ 只能被对半切 $\log \log n$ 次，所以如果跳查找的探查次数是常数，代价就是 $\Theta(\log \log n)$。

假设所需比较次数为 $i$，那么代价就是 $i$ （因为我们必须做 $i$ 次比较）。如果 $\mathbf{P}_i$ 是恰好需要 $i$ 次探查的概率，那么

\[\begin{split}\sum_{i=1}^{\sqrt{n}} i \mathbf{P}(\mbox{need exactly $i$ probes})\\ = 1 \mathbf{P}_1 + 2 \mathbf{P}_2 + 3 \mathbf{P}_3 + \cdots + \sqrt{n} \mathbf{P}_{\sqrt{n}}\end{split}\]

现在我们证明这与下式相同

\[\sum_{i=1}^{\sqrt{n}} \mathbf{P}(\mbox{need at least $i$ probes})\]

\[\begin{split}&=& 1 + (1-\mathbf{P}_1) + (1-\mathbf{P}_1-\mathbf{P}_2) + \cdots + \mathbf{P}_{\sqrt{n}}\\ &=& (\mathbf{P}_1 + ... + \mathbf{P}_{\sqrt{n}}) + (\mathbf{P}_2 + ... + \mathbf{P}_{\sqrt{n}}) +\\ && \qquad (\mathbf{P}_3 + ... + \mathbf{P}_{\sqrt{n}}) + \cdots\\ &=& 1 \mathbf{P}_1 + 2 \mathbf{P}_2 + 3 \mathbf{P}_3 + \cdots + \sqrt{n} \mathbf{P}_{\sqrt{n}}\end{split}\]

确定边界至少需要两次探查，因此代价为

\[2 + \sum_{i=3}^{\sqrt{n}} \mathbf{P}(\mbox{need at least $i$ probes}).\]

现在我们要利用一个名为切比雪夫不等式（Chebyshev's Inequality）的有用事实。切比雪夫不等式指出，$\mathbf{P}(\mbox{need exactly}\ i\ \mbox{probes})$，即 $\mathbf{P}_i$，满足

\[\mathbf{P}_i \leq \frac{p(1 - p)n}{(i - 2)^2 n} \leq \frac{1}{4(i-2)^2}\]

因为对任意概率 $p$ 都有 $p(1-p) \leq 1/4$。这假设数据是均匀分布的。因此，探查次数的期望值为

\[2 + \sum_{i=3}^{\sqrt{n}} \frac{1}{4(i-2)^2} < 2 + \frac{1}{4}\sum_{i=1}^\infty \frac{1}{i^2} = 2 + \frac{1}{4}\frac{\pi}{6} \approx 2.4112\]

QBS 比二分查找更好吗？理论上是的，因为 $O(\log \log n)$ 比 $O(\log n)$ 增长得慢。然而，这里的情况正说明了在某些实际情形下渐近复杂度模型的局限。确实，$c_1 \log n$ 增长得比 $c_2 \log \log n$ 快。事实上，是指数级地快！但即便如此，对于实际使用的输入规模，绝对代价的差异也相当小。因此，常数因子可能会起作用。首先把 $\log \log n$ 与 $\log n$ 进行比较。

\[\begin{split}\begin{array}{llll} &&&{\rm Factor}\\ n &\log n&\log \log n&{\rm Difference}\\ \hline 16 &4 &2 &2\\ 256&8 &3 &2.7\\ 2^{16}&16 &4 &4\\ 2^{32}&32 &5 &6.4\\ \end{array}\end{split}\]

降低算法的增长率并不总是切实可行的。每个问题都有一个实用窗口，因为我们想求解的输入能有多大是有一个实际限度的。如果我们的问题规模永远不会变得太大，那么能否再降低一个 log 因子的代价就无关紧要了，因为两种算法的常数因子之差可能比输入规模的对数再取对数还要大。

对这两种算法，让我们进一步看看到底用了多少次比较。二分查找总共需要大约 $\log n-1$ 次比较。二次二分查找大约需要 $2.4 \log \log n$ 次比较。如果把这一点加进我们的表格，就会看到相对差异完全是另一番图景。

\[\begin{split}\begin{array}{llll} &&&{\rm Factor}\\ n &\log n -1&2.4 \log \log n&{\rm Difference}\\ \hline 16&3&4.8&{\rm worse}\\ 256&7&7.2&\approx {\rm same}\\ 64K&15&9.6&1.6\\ 2^{32}&31&12&2.6 \end{array}\end{split}\]

但事情还没结束。这只是原始比较次数的统计。二分查找本质上比 QBS 简单得多，因为二分查找每次比较前只需计算数组的中点位置，而二次二分查找必须计算插值点，后者代价更高。所以 QBS 的常数因子还要更高。

QBS 不仅平均常数因子更差，而且想要表现良好，它对良好数据分布的依赖也远比二分查找强。例如，设想你在电话簿中查找名字"Young"。通常你会翻到书的靠后部分。如果找到的名字以 'Z' 开头，你可能会稍稍往前翻一点。如果接着找到的名字也以 'Z' 开头，你会再往前翻一些。如果这本电话簿很不寻常，一半的词条都以 'Z' 开头，那么你就需要多次往前翻，而每次只能从查找中排除相对较少的记录。在极端情况下，如果键值的分布被严重误判，插值查找的性能可能并不比顺序查找好多少。

虽然事实证明 QBS 并不是一种实用的算法，但这并不是典型情况。幸运的是，算法的增长率通常表现良好，因此渐近算法分析几乎总能就两种算法孰优孰劣给出实用的判断。

OpenDSA 完整目录

Chapter 22 Searching