作者：解学武

二分查找又称折半查找、二分搜索、折半搜索等，是一种在静态查找表中查找特定元素的算法。

所谓静态查找表，即只能对表内的元素做查找和读取操作，不允许插入或删除元素。

使用二分查找算法，必须保证查找表中存放的是有序序列（升序或者降序）。换句话说，存储无序序列的静态查找表，除非先对数据进行排序，否则不能使用二分查找算法。

二分查找算法的实现思路

二分查找算法非常简单，下面通过一个实例给大家讲解该算法的实现思路。

例如，在升序的查找表 {10, 14, 19, 26, 27, 31, 33, 35, 42, 44} 中查找元素 33。初始状态下，搜索区域为整个查找表，用 low 记录搜索区域内第一个元素的位置，用 high 记录搜索区域内最后一个元素的位置。


二分查找算法的查找过程是：
1) 借助 ⌊(low+high)/2⌋ 公式，找到搜索区域内的中间元素。图 1 中，搜索区域内中间元素的位置是 ⌊(1+10)/2⌋=5，因此中间元素是 27，此元素显然不是要找的目标元素。


整个查找表为升序序列，根据 27<33，可以判定 33 位于 27 右侧的区域，更新搜索区域为元素 27 右侧的区域。


2) 图 3 中，搜索区域内中间元素的位置是 ⌊(6+10)/2⌋=8，因此中间元素是 35，此元素不是要找的目标元素。


根据 35>33，可以判定 33 位于 35 左侧的区域，更新搜索区域。
3) 图 5 中，搜索区域内中间元素的位置是 ⌊(6+7)/2⌋=6，因此中间元素是 31，此元素不是要找的目标元素。


根据 31<33，可以判定 33 位于 31 右侧的区域，更新搜索区域。


4) 图 7 中，搜索区域内中间元素的位置是 ⌊(7+7)/2⌋=7，因此中间元素是 33，此元素就是要找的目标元素。


找到了目标元素 33，二分查找算法执行结束。下面的动画演示了整个二分查找算法的执行过程：


所谓二分查找算法，其实就是不断地将有序查找表“一分为二”，逐渐缩小搜索区域，进而找到目标元素。当查找表中没有目标元素时（比如图 8 中的元素 33 为 32），最终会出现 low>high 的情况，此时就表明查找表中没有目标元素，查找失败。

二分查找算法的具体实现

线性存储结构具体可以分为两类，分别是顺序表和单链表。采用顺序表表示静态查找表，二分查找算法更容易实现。

就以顺序表为例，实现二分查找算法的 C 语言程序如下：

#include <stdio.h>
#include <stdlib.h>
#define keyType int

typedef struct {
    keyType key; //查找表中每个数据元素的值
    //如果需要，还可以添加其他属性
}ElemType;

typedef struct {
    ElemType* elem; //存放查找表中数据元素的数组
    int length; //记录查找表中数据的总数量
}SSTable;

//创建查找表
void Create(SSTable* st, int length) {
    int i;
    st->length = length;
    st->elem = (ElemType*)malloc((length) * sizeof(ElemType));
    printf("输入表中的元素：\n");
    //根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据
    for (i = 0; i < length; i++) {
        scanf("%d", &(st->elem[i].key));
    }
}

//折半查找算法
int Search_Bin(SSTable ST, keyType key) {
    int low = 0; // 初始状态 low 指针指向第一个关键字
    int high = ST.length - 1; // high 指向最后一个关键字
    int mid;
    while (low <= high) {
        mid = (low + high) / 2; // int 本身为整形，所以 mid 每次为取整的整数
        if (ST.elem[mid].key == key) // 如果 mid 指向的同要查找的相等，返回 mid 所指向的位置
        {
            return mid;
        }
        else if (ST.elem[mid].key > key) // 如果mid指向的关键字较大，则更新 high 指针的位置
        {
            high = mid - 1;
        }
        // 反之，则更新 low 指针的位置
        else {
            low = mid + 1;
        }
    }
    //未在查找表中找到目标元素，查找失败
    return -1;
}

int main() {
    int len, key;
    int location;
    SSTable st = { 0 };
    printf("请输入查找表的长度：");
    scanf("%d", &len);
    Create(&st, len);
    printf("请输入查找数据的关键字：");
    scanf("%d", &key);
    location = Search_Bin(st, key);
    //如果返回值为 -1，证明查找表中未查到 key 值，
    if (location == -1) {
        printf("查找表中无目标元素");
    }
    else {
        printf("目标元素在查找表中的位置为：%d", location + 1);
    }
    free(st.elem);
    return 0;
}

程序的执行结果为：

请输入查找表的长度：10
输入表中的元素：
10 14 19 26 27 31 33 35 42 44
请输入查找数据的关键字：33
目标元素在查找表中的位置为：7

二分查找算法的性能分析

衡量二分查找算法的性能，可以计算它的时间复杂度，也可以计算它的平均查找长度（ASL）。

二分查找算法的时间复杂度可以用O(log2n)表示（n 为查找表中的元素数量，底数 2 可以省略）。和顺序查找算法的O(n)相比，显然二分查找算法的效率更高，且查找表中的元素越多，二分查找算法效率高的优势就越明显。

计算二分查找算法的平均查找长度，可以借助《什么是查找表》一节给出的公式：


默认情况下，表中各个元素被查找到的概率是相同的，都是 1/n（n 为查找表中元素的数量），所以各个元素对应的 Pi 都是 1/n。

二分查找过程中，各个元素对应的查找次数 C_i 可以借助一棵二叉树直观地看出来，通常称为“判定树”。例如图 9 对应的判定树为：


查找元素 33 的过程，恰好走了一条从根结点到结点 33 的路径，一共比较了 4 次。同样地，采用二分查找算法查找元素 19，整个过程需要比较 3 次。也就是说，查找表中各个元素对应的比较次数，恰好等于该元素所在判定树中的层数（元素 33 位于二叉树的第 4 层）。

对于包含 n 个元素的查找表，它对应的判定树最多有 ⌊log₂n⌋+1 层，第 h 层的元素个数最多有 2^h-1 个。

假设有序查找表的长度恰好为 n = 2^h-1，对应的判定树是一棵满二叉树，树中层数为 1（C₁=1）的结点有 1 个，层数为 2（C₂=2）的结点有 2 个，......，层数为 h（C_h=h）的结点有 2^h-1 个。则二分查找算法对应的 ASL 值为：

数学基础好的读者可自行推导，基础不好的读者也没必要纠结，知道结论即可，本节的重点是搞清楚二分查找算法的具体实现。

当查找表中的元素足够多时（n足够大），二分查找算法对应的 ASL 值近似等于 log₂(n+1)-1。

和顺序查找算法对应的 ASL 值 (n+1)/2 相比，二分查找算法的 ASL 值更小，可见后者的执行效率更高。

总结

二分查找算法的时间复杂度为O(logn)，平均查找长度 ASL=log₂(n+1)-1。和前面章节讲解的顺序查找算法相比，二分查找算法的执行效率更高。

二分查找算法只适用于有序的静态查找表，且通常选择用顺序表表示查找表结构。

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。