第16章 二分查找

16.1 问题从哪来#

前面几章用线性查找在数组里找学生：

for (int i = 0; i < count; i++) {         // 从第一个元素开始逐个遍历
    if (students[i].id == target) {    // 比较当前元素的学号与目标
        return i;                      // 找到，返回下标
    }
}
return -1;                             // 遍历完未找到，返回 -1

不管数组有没有排序，都是从第一个开始，一个一个比。10 万个学生，最坏情况要比较 10 万次。

但很多时候，数据是排好序的。比如学生按学号从小到大排好，电话簿按姓名排好，仓库货架按编号排好。排好序的数组有一个线性查找完全没用到的性质：如果中间那个元素比目标小，目标只可能在右半边；如果比目标大，只可能在左半边。

每次比较都能排除一大段候选位置。10 万个元素，$2^{17} = 131072$，最多 17 次就能确定目标在哪里，或者确定目标不存在。

16.2 先看一个例子#

假设有一组学号，已经从小到大排好：

索引：  0    1    2    3    4    5    6    7    8    9
学号： 12   25   33   41   57   64   78   82   91   96

要找学号 57。

第 1 步：看最中间那个。low = 0，high = 9，mid = (0 + 9) / 2 = 4，ids[4] = 57。正好等于目标，找到了，返回索引 4。

这个目标刚好在第一次检查的位置。换一个没那么巧的：找学号 82。

第 1 步：low = 0，high = 9，mid = 4，ids[4] = 57。57 比 82 小，说明 82 在右半边。low 移到 mid + 1 = 5。

候选范围缩到右半边：索引 5 到 9，对应学号 64、78、82、91、96。

第 2 步：mid = (5 + 9) / 2 = 7，ids[7] = 82。等于目标，找到。

只用了两次比较。如果用线性查找，要比较 8 次（从索引 0 一直比到索引 7）。

再看一个找不到的情况：找学号 60。

第 1 步：mid = 4，ids[4] = 57。57 比 60 小，low = 5。

第 2 步：mid = (5 + 9) / 2 = 7，ids[7] = 82。82 比 60 大，high = 6。

第 3 步：mid = (5 + 6) / 2 = 5，ids[5] = 64。64 比 60 大，high = 4。

现在 low = 5，high = 4，low > high，区间为空。目标不存在，返回 -1。

16.3 最小实验#

#include <stdio.h>

// 在已排序的数组 ids 中查找 target
// 找到返回索引，找不到返回 -1
int binary_search(int ids[], int count, int target)
{
    int low = 0;                    // 查找范围的左边界
    int high = count - 1;           // 查找范围的右边界

    while (low <= high) {           // 区间不为空就继续
        int mid = low + (high - low) / 2;   // 中间位置
        if (ids[mid] == target) {
            return mid;             // 找到了
        } else if (ids[mid] < target) {
            low = mid + 1;          // 目标在右半边
        } else {
            high = mid - 1;         // 目标在左半边
        }
    }
    return -1;                      // 区间为空，没找到
}

int main(void)
{
    int ids[] = {12, 25, 33, 41, 57, 64, 78, 82, 91, 96};
    int count = sizeof(ids) / sizeof(ids[0]);

    int targets[] = {57, 82, 60, 96, 10};
    int n = sizeof(targets) / sizeof(targets[0]);

    for (int i = 0; i < n; i++) {
        int pos = binary_search(ids, count, targets[i]);
        if (pos != -1) {
            printf("ID %d at index %d\n", targets[i], pos);
        } else {
            printf("ID %d not found\n", targets[i]);
        }
    }
    return 0;
}

binary_search 函数接收三个参数：排好序的数组 ids、元素个数 count、要找的目标 target。返回找到的索引，找不到返回 -1。

中间位置的计算用了 low + (high - low) / 2 而不是 (low + high) / 2。数组不大时，两种写法通常得到同一个 mid；但 low + high 在两个大数相加时可能超出 int 能表示的范围，算出来的 mid 就不可靠。low + (high - low) / 2 先算左右边界之间的距离，再加回左边界，更安全。

16.4 编译运行#

保存成 binary_search.c，编译：

$ gcc binary_search.c -o binary_search

运行：

ID 57 at index 4
ID 82 at index 7
ID 60 not found
ID 96 at index 9
ID 10 not found

5 个目标，3 个找到，2 个没找到。学号 96 是数组最后一个元素，线性查找要比较 10 次，二分查找用了 4 次：57、82、91、96。

16.5 数据/内存/流程里发生了什么#

16.5.1 low、mid、high 三个位置#

二分查找的核心就是三个变量：

每次循环，mid 指向当前范围的中间。拿 ids[mid] 和目标比较，有三种结果：

16.5.2 目标在左半边#

当 ids[mid] > target 时，目标只可能在 mid 的左边。把 high 移到 mid - 1，右边界收窄：

mid 本身也不用再看了——已经比过了，不等于目标。

16.5.3 目标在右半边#

当 ids[mid] < target 时，目标只可能在 mid 的右边。把 low 移到 mid + 1，左边界收窄：

16.5.4 找不到：区间变空#

每次循环，查找范围至少缩小一个元素（mid 被排除了）。当 low > high 时，左边界跑到了右边界的右边，区间为空。

这就是 while (low <= high) 的含义——low == high 时区间还有一个元素，要继续检查；low > high 时区间为空，退出循环。

16.5.5 比较次数#

每次循环都把候选范围缩小到大约一半。$n$ 个元素的数组，最坏比较次数和 $\log_2 n$ 同一个级别。更精确地说，n >= 1 时，最多比较 $\lfloor \log_2 n \rfloor + 1$ 次：

100 万个元素，线性查找最坏比较 100 万次，二分查找最多 20 次。这就是利用"有序"这个信息带来的加速。

这种增长速度通常写作 $O(\log n)$。它的意思不是精确等于某个次数，而是说：数据量翻倍时，二分查找通常只多比较 1 次左右。

16.5.6 用学生记录做二分查找#

把学号数组换成学生结构体数组时，循环框架不变。真正变化的是比较位置：原来比较 ids[mid]，现在比较 students[mid].id。

struct Student {
    int id;
    char name[32];
    int score;
};

// 按学号在已排序的学生数组中二分查找
int binary_search_student(struct Student students[], int count, int target_id)
{
    int low = 0;
    int high = count - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (students[mid].id == target_id) {
            return mid;                     // 找到了
        } else if (students[mid].id < target_id) {
            low = mid + 1;                  // 目标在右半边
        } else {
            high = mid - 1;                 // 目标在左半边
        }
    }
    return -1;                              // 没找到
}

调用时，返回值仍然是数组下标。拿到下标以后，就能访问这一整条学生记录：

struct Student students[] = {
    {1001, "Alice", 92},
    {1003, "Bob", 78},
    {1005, "Carol", 85},
    {1008, "Dave", 90},
    {1012, "Eve", 88},
};
int count = sizeof(students) / sizeof(students[0]);

int target_id = 1005;
int pos = binary_search_student(students, count, target_id);
if (pos != -1) {
    printf("Found ID %d: %s, Score %d\n",
           target_id, students[pos].name, students[pos].score);
}

运行：

Found ID 1005: Carol, Score 85

比较的是 students[mid].id 和 target_id，但返回的是 mid，也就是整个结构体在数组中的位置。拿到位置后，名字、分数等字段都能直接访问。

16.6 常见坑#

坑 1：数组没排序就用二分查找。

二分查找的前提是数组有序。如果数组没排序，二分查找的结果不可靠——它可能排除掉包含目标的那一半。

警告：二分查找只能用在已排序的数组上。如果不确定数组是否有序，先排序再查找。

坑 2：while 条件写成 low < high。

while (low < high) {    // 错！会漏掉 low == high 的情况

当 low == high 时，区间还有一个元素。写成 low < high 会跳过这个元素，导致漏查。正确写法是 low <= high。

坑 3：mid 计算溢出。

int mid = (low + high) / 2;     // low + high 可能溢出

当 low 和 high 都接近 INT_MAX 时，low + high 可能超出 int 能表示的范围，结果不可靠，可能算出错误的 mid。安全写法：

int mid = low + (high - low) / 2;   // 避免 low + high 溢出

坑 4：边界更新时没有加减 1。

low = mid;      // 错！死循环
high = mid;     // 错！死循环

找到 ids[mid] 不等于目标后，mid 已经检查过了，不需要再看。如果写成 low = mid 或 high = mid，下一次循环 mid 可能不变，区间不缩小，死循环。

正确写法是 low = mid + 1 或 high = mid - 1，把已经排除的 mid 跳过。

坑 5：返回值搞混。

binary_search 返回 -1 表示没找到。调用方要先判断：

int pos = binary_search(ids, count, target);
if (pos != -1) {
    // 找到了，用 ids[pos]
} else {
    // 没找到
}

如果忘记判断，直接用 ids[pos]，pos 为 -1 时会访问 ids[-1]，这是越界访问。

16.7 自己试试看#

Q1：修改前面的小实验。 在 10 个学号的数组中分别查找学号 33 和 100。打印每次循环的 low、mid、high 和 ids[mid] 的值，观察查找过程。

Q2：计数比较次数。 给 binary_search 加一个功能，返回前打印总共比较了多少次。分别用 10 个、100 个、1000 个元素的数组测试，观察比较次数的增长速度。

Q3：找第一个出现的位置。 如果数组里有重复元素，比如 {1, 3, 3, 3, 5}，标准的二分查找可能返回任意一个 3 的位置。修改函数，让它返回第一个 3 出现的位置（索引 1）。

Q4：猜数字游戏。 写一个程序，随机生成一个 1 到 1000 的整数，让用户猜。每次用户输入后，告诉用户猜大了、猜小了还是猜对了。统计猜了多少次。然后修改程序，让用户每次输入"大"或"小"，程序用二分查找策略自动猜——看看是不是最多 10 次就能猜到。

下一章的问题#

二分查找快，但它有一个隐含要求：数据存在数组里，而且必须保持有序。

如果要往数组中间插入一个新学号，比如在 {12, 25, 33, 41, 57} 中插入 30，需要把 33、41、57 全部往后挪一格。10 万条记录，在中间插入就要移动 5 万次。

数组查找快，但插入和删除要搬动元素。链表插入和删除不用搬动一整段数组，但不能按下标直接跳到中间，也没法用二分查找。有没有一种结构，既能利用大小关系查找，又能减少中间插入时搬动元素？