Question

我们在讲树结构的二叉树定义（本书第6.5节）时，曾经提到过一个小游戏，我在纸上已经写好了一个100以内的正整数数字请你猜，问几次可以猜出来，当时已经介绍了如何最快猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找，如图8-4-1所示。

图8-4-1

折半查找（Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

假设我们现在有这样一个有序表数组{0,1,16,24,35,47,59,62,73,88,99}，除0下标外共10个数字。对它进行查找是否存在62这个数。我们来看折半查找的算法是如何工作的。

/* 折半查找 */
int Binary_Search(int *a, int n, int key)
{
    int low, high, mid;
    /* 定义最低下标为记录首位 */
    low = 1;                       
    /* 定义最高下标为记录末位 */
    high = n;                      
    while (low <= high)
    {
        /* 折半 */
        mid = (low + high) / 2;    
        /* 若查找值比中值小 */
        if (key < a[mid])          
           /* 最高下标调整到中位下标小一位 */
           high = mid - 1;        
        /* 若查找值比中值大 */
        else if (key > a[mid])     
            /* 最低下标调整到中位下标大一位 */
            low = mid + 1;         
        else
            /* 若相等则说明mid即为查找到的位置 */
            return mid;            
    }
    return 0;
}

1．程序开始运行，参数a={0,1,16,24,35,47,59,62,73,88,99}，n=10，key=62，第3～5行，此时low=1，high=10，如图8-4-2所示。

图8-4-2

2．第6～15行循环，进行查找。

3．第8行，mid计算得5，由于a[5]=47<key，所以执行了第12行，low=5+1=6，如图8-4-3所示。

图8-4-3

4．再次循环，mid=(6+10)/2=8，此时a[8]=73>key，所以执行第10行，high=8-1=7，如图8-4-4所示。

图8-4-4

5．再次循环，mid=(6+7)/2=6，此时a[6]=59<key，所以执行12行，low=6+1=7，如图8-4-5所示。

图8-4-5

6．再次循环，mid=(7+7)/2=7，此时a[7]=62=key，查找成功，返回7。

该算法还是比较容易理解的，同时我们也能感觉到它的效率非常高。但到底高多少？关键在于此算法的时间复杂度分析。

首先，我们将这个数组的查找过程绘制成一棵二叉树，如图8-4-6所示，从图上就可以理解，如果查找的关键字不是中间记录47的话，折半查找等于是把静态有序查找表分成了两棵子树，即查找结果只需要找其中的一半数据记录即可，等于工作量少了一半，然后继续折半查找，效率当然是非常高了。

图8-4-6

我们之前6.6节讲的二叉树的性质4，有过对“具有n个结点的完全二叉树的深度为。”性质的推导过程。在这里尽管折半查找判定二叉树并不是完全二叉树，但同样相同的推导可以得出，最坏情况是查找到关键字或查找失败的次数为。

有人还在问最好的情况？那还用说吗，当然是1次了。

因此最终我们折半算法的时间复杂度为O(logn)，它显然远远好于顺序查找的O(n)时间复杂度了。

不过由于折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，这样的算法已经比较好了。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。