《算法基础：打开算法之门》一3.1 二分查找

本节书摘来自华章出版社《算法基础：打开算法之门》一书中的第3章，第3.1节，作者 ［美］托马斯 H 科尔曼（Thomas H Cormen），更多章节内容可以访问云栖社区“华章计算机”公众号查看

3.1 二分查找

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

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

下面讲述如何运用二分查找方法来查找由Jonathan Swift所写的书。准确地确定书架的正中间位置，并查看该位置的书籍，检查作者的名字。假定你找到了一本由Jack London所写的书。这时你不仅仅知道这本书不是你要找的书籍，而且因为你知道所有的书都是按照作者姓名字母顺序排序的，那么你就会知道位于London所写的书的左侧的所有书籍均不可能是你要寻找的。仅仅通过查看一本书，你就可以考虑淘汰书架上的一半书籍！任何由Swift所写的书籍必定位于书架的右半部分。若此时你找到了位于右侧的那一半书籍正中点位置的书籍。现假定该书籍是由Leo Tolstoy所写的。同样，这本书也不是你要查找的书籍，但是你可以淘汰这本书右侧的所有书籍：保留余下的那一半有可能的书籍。这时候你知道如果书架上包含由Swift所写的书，那么它一定在剩下的四分之一份书籍中，即介于London右侧和Tolstoy左侧的书之间。下一次，你找到位于这余下四分之一书籍的正中间的位置的书籍并判定它是否是要查找的书籍。如果你发现它是由Swift所写的，28那么你就完成了查找任务。否则，你需要再一次淘汰当前书籍中的一半书籍。最终，你或许找到了一本由Swift所写的书或者剩下的书籍均不可能是要查找的书籍。在后一种情况中，你可以断定书架上不包含由Jonathan Swift所写的书籍。
在计算机中，我们在一个数组上执行二分查找。在任意情况下，我们仅仅考虑某个子数组，也就是说，介于两个索引之间的部分数组，将这两个索引依次记为p和r。初始时，p=1,r=n，因此开始时，子数组为整个完整数组。我们反复地将子数组规模减半，直到发现以下任意一种情况发生：要么找到了要查找的元素，要么当前的子数组为空（也就是说，p变得大于r）。反复对子数组执行减半操作需要花费O（lgn）的运行时间。

下面是执行二分查找的详尽过程。例如，我们要在数组A中查找值x。在每一步中，我们仅仅考虑以A［p］开始、A［r］结束的子数组。由于经常操作子数组，我们将该子数组表示为A［pr］。在每一步中，通过取p和r的平均数且舍弃分数部分来计算出当前正在考虑的子数组的中间位置q，对于任何情况，都有q=(p+r)/2。（这里，我们使用“向下取整”符号来舍弃分数部分。如果你将在某一编程语言中实现该符号，例如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］这个位置及位于它之后的所有元素：我们令p保持不变，而r被设为q-1，开始下一步：

如果反之，我们发现A［q］

以下是二叉查找的精确

第二步的循环不一定因为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，因此当程序首先进入循环时，循环不变式为真。
保持：我们证明上述第2C步和第2D步中正确地调整p或者r。30
终止：如果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（lgn)时间。一个重要的观察结果是：当前子数组的规模r-p+1在每次循环迭代中均近似减半（或者在递归版本的每次递归调用中子数组均会近似减半，但是这里让我们只考虑迭代版本的BINARYSEARCH程序）。尝试了所有情况后，你将会发现如果一次迭代开始于一个具有s个元素的子数组，那么下一次迭代将会有s/2或者s/2-1个元素，这取决于s是偶数还是奇数以及A［q］大于还是小于x。31我们已经看到一旦子数组的规模降到了1，那么程序将会终止于下一次迭代。因此我们会问，需要多少次子数组减半的循环迭代操作才能将一个初始规模为n的数组降为一个规模为1的数组？那将和以规模为1的子数组开始，每一次将它的规模加倍直到规模为n所需要的次数是相同的。后者仅仅是取幂，即反复地乘以2。换句话说，使得2x等于n的x应该是多少？如果n是2的整数幂，那么我们已经在14节计算出这个值是lgn。当然，n可能不是2的整数幂，在这种情况下，这个值可能在1和lgn之间。最后，我们指出循环的每次迭代需要花费常量时间，也就是说，一次简单迭代的时间并不依赖于原始数组的规模n和当前正在考虑的子数组的规模。让我们使用近似符号来忽略常量因子和低阶项。（循环迭代的次数是lgn还是lgn+1呢？有谁会关心呢？）因此我们得出了二分查找的运行时间是O（lgn)。
在这里，使用O符号是因为我想得出一个能够涵盖所有情况的结果。在最坏情况下，当值x并没有在数组中出现时，我们迭代地进行减半操作，直到当前正在考察的子数组等于空为止，这会产生Θ（lgn）的运行时间。在最好情况下，即x在循环的第一次迭代过程中，那么此时运行时间是Θ（1）。Θ符号不会覆盖所有的情况，但是O（lgn）的运行时间对于二分查找而言总是正确的——只要数组已经是有序的。
对于查找而言，最坏运行时间可能超越Θ（lgn）吗？除非我们采取更详细的数据组织方式，并且对关键字做出一定的假设。