3.1 二分查找

在学习一些排序算法之前，首先学习二分查找，其中待查找的数组事先需要是有序的。二分查找的优点是从包含 n 个元素的数组中执行查找操作仅仅需要 O （lg n ）时间。

在书架那个例子中，当书架上的书已经按照作者名字从左向右依次排好序后才开始进行查找。我们将使用作者名字作为主关键字，现在让我们搜索下由Jonathan Swift所写的书。你可能已经推测到：因为作者的姓以“S”开头，“S”是字母表中的第19个字母，且19/26与3/4接近，因此你可能会浏览书架上位置大约在四分之三的那部分书籍。但是如果你有莎士比亚的所有作品，接着还有几本姓氏排在Swift之前的作者的书籍，就会使Swift的书所处的位置比你设想的位置靠右些。

28

下面讲述如何运用二分查找方法来查找由Jonathan Swift所写的书。准确地确定书架的正中间位置，并查看该位置的书籍，检查作者的名字。假定你找到了一本由Jack London所写的书。这时你不仅仅知道这本书不是你要找的书籍，而且因为你知道所有的书都是按照作者姓名字母顺序排序的，那么你就会知道位于London所写的书的左侧的所有书籍均不可能是你要寻找的。仅仅通过查看一本书，你就可以考虑淘汰书架上的一半书籍！任何由Swift所写的书籍必定位于书架的右半部分。若此时你找到了位于右侧的那一半书籍正中点位置的书籍。现假定该书籍是由Leo Tolstoy所写的。同样，这本书也不是你要查找的书籍，但是你可以淘汰这本书右侧的所有书籍：保留余下的那一半有可能的书籍。这时候你知道如果书架上包含由Swift所写的书，那么它一定在剩下的四分之一份书籍中，即介于London右侧和Tolstoy左侧的书之间。下一次，你找到位于这余下四分之一书籍的正中间的位置的书籍并判定它是否是要查找的书籍。如果你发现它是由Swift所写的，那么你就完成了查找任务。否则，你需要再一次淘汰当前书籍中的一半书籍。最终，你或许找到了一本由Swift所写的书或者剩下的书籍均不可能是要查找的书籍。在后一种情况中，你可以断定书架上不包含由Jonathan Swift所写的书籍。

在计算机中，我们在一个数组上执行二分查找。在任意情况下，我们仅仅考虑某个子数组，也就是说，介于两个索引之间的部分数组，将这两个索引依次记为 p 和 r 。初始时， p =1, r = n ，因此开始时，子数组为整个完整数组。我们反复地将子数组规模减半，直到发现以下任意一种情况发生：要么找到了要查找的元素，要么当前的子数组为空（也就是说， p 变得大于 r ）。反复对子数组执行减半操作需要花费 O （lg n ）的运行时间。

下面是执行二分查找的详尽过程。例如，我们要在数组 A 中查找值 x 。在每一步中，我们仅仅考虑以 A [ p ]开始、 A [ r ]结束的子数组。由于经常操作子数组，我们将该子数组表示为 A [ p .. r ]。在每一步中，通过取 p 和 r 的平均数且舍弃分数部分来计算出当前正在考虑的子数组的中间位置 q ，对于任何情况，都有 。（这里，我们使用“向下取整”符号 来舍弃分数部分。如果你将在某一编程语言中实现该符号，例如Java、C或者C++，那么你可以使用整除符号来舍弃分数部分。）我们判断 A [ q ]是否等于 x ，如果 A [ q ]确实等于 x ，那么我们就完成了查找操作，因为 q 是数组 A 中一个包含 x 的索引，我们可以将其返回。

如果反之，我们发现 A [ q ]≠ x ，那么我们可以利用 A 是有序的这个假设。由于 A [ q ]≠ x ，这里存在两种可能，或者是 A [ q ]> x ，或者是 A [ q ]< x 。我们首先处理 A [ q ]> x 这种情况。因为数组是有序的，我们知道不仅仅 A [ q ]比 x 大，而且——考虑到数组从左到右按顺序排列——排在 A [ q ]之后的每个数组元素均比 x 大。因此，我们能够淘汰所有在 A [ q ]这个位置及位于它之后的所有元素：我们令 p 保持不变，而 r 被设为 q -1，开始下一步：

29

如果反之，我们发现 A [ q ]< x ，我们知道每个数组在 A [ q ]或者 A [ q ]左侧的数组元素均比 x 小，因此淘汰这些元素（即在 A [ q ]位置和 A [ q ]左侧的元素）。令 r 保持不变，而 p 被设定为 q +1，开始下一步：

以下是二叉查找的精确程序BINARY-SEARCH：

第二步的循环不一定因为 p 变得比 r 大而终止，如果它发现 A [ q ]等于 x ，则会在第2B步终止，并返回 A 中等于 x 元素的对应索引 q 。

为了证明BINARY-SEARCH程序能正确地运行，仅仅需要展示如果BINARY-SEARCH在第3步中返回NOT-FOUND，那么 x 不会出现在数组的任意位置。使用如下的循环不变式：

在第 2 步循环的每一次迭代开始时 ， 如果 x 出现在数组 A 中的某个位置 ， 那么它在子数组 A [ p .. r ] 的某个位置处 。

使用循环不变式的简洁证明如下：

初始化： 第1步分别将索引 p 初始化为1， r 初始化为 n ，因此当程序首先进入循环时，循环不变式为真。

30

保持： 我们证明上述第2C步和第2D步中正确地调整 p 或者 r 。

终止： 如果 x 不在数组中，那么最终程序会找到 p = r 的位置。如果 p = r ，第2A步计算出的 q 会与 p 和 r 均相等。如果第2C步中将 r 设定为 q -1，那么在下一次迭代开始时， r 将会等于 p -1，那么 p 会大于 r 。如果第2D步中将 p 设定为 q +1，那么在下一次迭代开始时， p 会等于 r +1，同样地 p 会大于 r 。任何一种情况下，第2步中的循环判定均会是错误的，并且循环会终止。因为 p > r ，那么子数组 A [ p .. r ]将会是空的，因此值 x 不可能出现在子数组中。参考循环不变式2.3节的等价命题给我们的指示：如果 x 并没有出现在子数组 A [ p .. r ]中，那么它不可能出现在数组 A 的任何位置。因此，第3步中返回NOT-FOUND是正确的。

我们也能将二叉查找写成递归程序：

初始调用是RECURSIVE-BINARY-SEARCH（ A ,1, n , x ）。

现在证明在一个 n 元素数组上二叉查找需要 O （lg n ）时间。一个重要的观察结果是：当前子数组的规模 r-p +1在每次循环迭代中均近似减半（或者在递归版本的每次递归调用中子数组均会近似减半，但是这里让我们只考虑迭代版本的BINARY-SEARCH程序）。尝试了所有情况后，你将会发现如果一次迭代开始于一个具有 s 个元素的子数组，那么下一次迭代将会有 或者 s /2-1个元素，这取决于 s 是偶数还是奇数以及 A [ q ]大于还是小于 x 。我们已经看到一旦子数组的规模降到了1，那么程序将会终止于下一次迭代。因此我们会问，需要多少次子数组减半的循环迭代操作才能将一个初始规模为 n 的数组降为一个规模为1的数组？那将和以规模为1的子数组开始，每一次将它的规模加倍直到规模为 n 所需要的次数是相同的。后者仅仅是取幂，即反复地乘以2。换句话说，使得2 ^x 等于 n 的 x 应该是多少？如果 n 是2的整数幂，那么我们已经在1.4节计算出这个值是lg n 。当然， n 可能不是2的整数幂，在这种情况下，这个值可能在1和lg n 之间。最后，我们指出循环的每次迭代需要花费常量时间，也就是说，一次简单迭代的时间并不依赖于原始数组的规模 n 和当前正在考虑的子数组的规模。让我们使用近似符号来忽略常量因子和低阶项。（循环迭代的次数是lg n 还是 呢？有谁会关心呢？）因此我们得出了二分查找的运行时间是 O （lg n ）。

31

在这里，使用 O 符号是因为我想得出一个能够涵盖所有情况的结果。在最坏情况下，当值 x 并没有在数组中出现时，我们迭代地进行减半操作，直到当前正在考察的子数组等于空为止，这会产生Θ（lg n ）的运行时间。在最好情况下，即 x 在循环的第一次迭代过程中，那么此时运行时间是Θ（1）。Θ符号不会覆盖所有的情况，但是 O （lg n ）的运行时间对于二分查找而言总是正确的——只要数组已经是有序的。

对于查找而言，最坏运行时间可能超越Θ（lg n ）吗？除非我们采取更详细的数据组织方式，并且对关键字做出一定的假设。 d0X1rL+74aUmZWuCGk34yuGRdS3BY+wfhZToYnJZ690C6tiWynVNKfnsBMY80OFq