折半查找

对于有序数组的查找，折半查找性能卓越。它通过比较查找键K和数组中间元素A[m]来完成查找工作。如果它们相等，算法结束；否则，如果K < A[m],就对数组的前半部分执行该操作，如果K > A[m],则对数组的后半部分执行该操作。

虽然折半查找是基于递归的思想，但是它也可以以非递归算法的形式实现。这里有一段非递归版本的伪代码:

算法 BinarySearch(A[0..n-1],K)
    //实现非递归的折半查找
    //输入：一个升序数组A[0..n-1]和一个查找键K
    //输出：一个数组元素的下标，该元素等于K；如果没有这样一个元素，则返回-1
    l <- 0; r <- n-1
    while l ≦ r do
        m <- [(l+r)/2]
        if K = A[m] return m
        else if K < A[m] r <- m-1
        else l <- m+1
    return -1

分析折半查找效率的标准方法是查找键和数组元素的比较次数。为了简单起见，我们计算三路比较的次数。三路比较假设，对K和A[m]进行一次比较以后，算法就能判断出K是大于，小于还是等于A[m].

对于一个n元素的数组来说，该算法需要进行多少次比较呢？

问题的答案不仅取决于n，而且取决于特定输入的特征。让我们先来求最坏情况下需要进行的键值比较次数Cw(n).最坏输入包括所有那些不包含查找键K的数组。在进行了一次比较以后，数组规模变成了原来的二分之一，然后继续面临着同样的情况，于是对于Cw(n)我们有下面的递推关系式：

当 n > 1时，Cw(n) = Cw([n/2])+1, Cw(1) = 1 (4.2)

就像2.4节中提到的那样，解(4.2)这样的递推式的标准方法是先假设n=2^k, 然后用反向替换法或者其他的方法来对引出的递推式求解。

Cw(2^k) = k+1 = log2 n +1 (4.3)

公式(4.3)在n＝2^k时给出的解，经过调整以后可以适用于任意的正整数n:

Cw(n) = [log2 n]+1 = [log2(n+1)] (4.4)

替换法证明，对于大于0的任意偶数n来说，Cw(n)=[log2 n] + 1确实满足等式(4.2)。如果n是一个大于0的正整数，当i > 0时，n＝2i。当n＝2i时，等式(4.2)的左边为：

Cw(n) = [log2 n]+1 = [log2 2i]+1 = [log2 2 + log2 i]+1
= (1+[log2 i])+1 = [log2 i]+2

当n＝2i时，等式(4.2)的右边为：

Cw([n/2])+1 = Cw([2i/2])+1 = Cw(i)+1
= ([log2 i]+1)+1 = [log2 i]+2

既然两个表达式都相同，该命题得证。

折半查找得最差效率属于集合Θ(logn).

折半查找得平均效率是怎么样的呢？

一个复杂的分析指出，折半查找的平均键值比较次数仅比最差的情况有轻微的改善：

Cavg(n) ≈ log2 n

就依赖键值比较操作的查找算法而言（参见10.2节决策树），折半查找已经是一种最优的查找算法了，但还有一些查找算法具有更优的平均效率（5.6节介绍了插值查找；7.3节介绍了散列查找）其中散列查找甚至不需要它的输入是有序的。折半查找所包含的思想不仅仅能应用于查找，还可以对一元非线性方程求解；11.4节在讨论两分法的时候，会介绍折半查找的一系列其他应用。

在结束本节之前，我们还要对折半查找再做一点说明。折半查找有时是作为分治算法的精粹案例来呈现的。但这种认识存在误区，因为实际上，折半查找是分治法的宇哥非常不典型的特例。根据本章开头所下的定义，分治技术把一个问题划分为若干个子问题，每一个子问题，都需要分别求解。对于折半查找来说则不然，两个子问题中只有一个需要求解。实事求是地讲，折半查找更适合归类到减半算法，我们会在5.5节讨论这类算法。

那么本章为什么饿要讨论折半查找呢？

部分是因为遵循传统，部分是因为，有时候一个坏的例子比一个好的例子更能够说明一个道理。