折半查找，也称二分查找，在某些情况下相比于顺序查找，使用折半查找算法的效率更高。但是该算法的使用的前提是静态查找表中的数据必须是有序的。

例如，在{5,21,13,19,37,75,56,64,88 ,80,92}这个查找表使用折半查找算法查找数据之前，需要首先对该表中的数据按照所查的关键字进行排序：{5,13,19,21,37,56,64,75,80,88,92}。

在折半查找之前对查找表按照所查的关键字进行排序的意思是：若查找表中存储的数据元素含有多个关键字时，使用哪种关键字做折半查找，就需要提前以该关键字对所有数据进行排序。

折半查找算法
对静态查找表{5,13,19,21,37,56,64,75,80,88,92}采用折半查找算法查找关键字为 21 的过程为：

如上图所示，指针 low 和 high 分别指向查找表的第一个关键字和最后一个关键字，指针 mid 指向处于 low 和 high 指针中间位置的关键字。在查找的过程中每次都同 mid 指向的关键字进行比较，由于整个表中的数据是有序的，因此在比较之后就可以知道要查找的关键字的大致位置。

例如在查找关键字 21 时，首先同 56 作比较，由于21 < 56，而且这个查找表是按照升序进行排序的，所以可以判定如果静态查找表中有 21 这个关键字，就一定存在于 low 和 mid 指向的区域中间。

因此，再次遍历时需要更新 high 指针和 mid 指针的位置，令 high 指针移动到 mid 指针的左侧一个位置上，同时令 mid 重新指向 low 指针和 high 指针的中间位置。如图所示：

同样，用 21 同 mid 指针指向的 19 作比较，19 < 21，所以可以判定 21 如果存在，肯定处于 mid 和 high 指向的区域中。所以令 low 指向 mid 右侧一个位置上，同时更新 mid 的位置。

当第三次做判断时，发现 mid 就是关键字 21 ，查找结束。

注意：在做查找的过程中，如果 low 指针和 high 指针的中间位置在计算时位于两个关键字中间，即求得 mid 的位置不是整数，需要统一做取整操作。

折半查找的实现代码：

//折半查找算法
int Binary_Search(SeqList L, ElemType key) {
    int low = 1;　　//初始状态 low 指向第一个关键字
    int high = L.length;　　//high 指向最后一个关键字
    int mid;
    while (low <= high) {
        mid = (low+high) / 2;　　// int 本身为整形，所以，mid 每次为取整的整数
        if (L.elem[mid].key == key)// 如果 mid 指向的同要查找的相等，返回 mid 所指向的位置
            return mid;
        else if(L.elem[mid].key > key)// 如果mid指向的关键字较大，则更新 high 的位置
            high = mid-1;
        else // 反之，则更新 low 的位置
            low = mid + 1;
...

课后习题

【2017年真题】下列二叉树中，可能成为折半查找判定树（不含外部结点）的是（）

参考答案：A

【2015年真题】下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500,200,450,180    B．500,450,200,180
C．180,500,200,450    D．180,200,500,450

参考答案：A

【2010年真题】已知一个长度为 16 的顺序表 L，其元素按关键字有序排列。若采用折半查 找法查找一个 L 中不存在的元素，则关键字的比较次数最多的是（）。 
A．4 B．5 C．6 D．7 

参考答案：B
答案解析：考查折半查找的过程。 
具有 n 个结点的判定树的高度为log2n + 1，长度为 16，高度为 5，所以最多比较 5 次。