我们在讲树结构的二叉树定义（本书第6.5节）时，曾经提到过一个小游戏，我在纸上已经写好了一个100以内的正整数数字请你猜，问几次可以猜出来，当时已经介绍了如何最快猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找，如图8-4-1所示。
    image.png
    折半查找（Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间
    记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

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

    1. /* 折半查找 */
    2. int Binary_Search(int *a, int n, int key){
    4.     int low, high, mid;
    6.     /* 定义最低下标为记录首位 */
    7.     low = 1;
    8.     /* 定义最高下标为记录末位 */
    9.     high = n;
    11.     while (low <= high){
    13.         /* 折半 */
    14.         mid = (low + high) / 2;
    16.         /* 若查找值比中值小 */
    17.         if (key < a[mid])
    18.             /* 最高下标调整到中位下标小一位 */
    19.             high = mid - 1;
    20.         /* 若查找值比中值大 */
    21.         else if (key > a[mid])
    22.             /* 最低下标调整到中位下标大一位 */
    23.             low = mid + 1;
    24.         else
    25.             /* 若相等则说明mid即为查找到的位置 */
    26.             return mid;
    27.     }
    29.     return 0;
    30. }
    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所示。

    image.png

    1. 第6～15行循环，进行查找。
    2. 第8行，mid计算得5，由于a[5]=47<key，所以执行了第12行，low=5+1=6，如图8-4-3所示。

    image.png

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

    image.png

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

    image.png

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

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

    首先，我们将这个数组的查找过程绘制成一棵二叉树，如图8-4-6所示，从图上就可以理解，如果查找的关键字不是中间记录47的话，折半查找等于是把静态有序查找表分成了两棵子树，即查找结果只需要找其中的一半数据记录即可，等于工作量少了一半，然后继续折半查找，效率当然是非常高了。
    image.png
    我们之前6.6节讲的二叉树的性质4，有过对“具有n个结点的完全二叉树的深度为。”性质的推导过程。在这里尽管折半查找判定二叉树并不是完全二叉树，但同样相同的推导可以得出，最坏情况是查找到关键字或查找失败的次数为。

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

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

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