一站式学习 C 编程

主题

6. 折半查找 ​

如果不是从一组随机的序列里查找，而是从一组排好序的序列里找出某个元素的位置，则可以有更快的算法：

例 11.4. 折半查找

c
#include <stdio.h>

#define LEN 8
int a[LEN] = {1, 2, 2, 2, 5, 6, 8, 9};

int binarysearch(int number) {
    int mid, start = 0, end = LEN - 1;

    while (start <= end) {
        mid = (start + end) / 2;
        if (a[mid] < number)
            start = mid + 1;
        else if (a[mid] > number)
            end = mid - 1;
        else
            return mid;
    }
    return -1;
}

int main(void) {
    printf("%d\n", binarysearch(5));
    return 0;
}

由于这个序列已经从小到大排好序了，每次取中间的元素和待查找的元素比较，如果中间的元素比待查找的元素小，就说明“如果待查找的元素存在，一定位于序列的后半部分”，这样可以把搜索范围缩小到后半部分，然后再次使用这种算法迭代。这种“每次将搜索范围缩小一半”的思想称为折半查找（Binary Search）。思考一下，这个算法的时间复杂度是多少？

这个算法的思想很简单，不是吗？可是 编程珠玑 上说作者在课堂上讲完这个算法的思想然后让学生写程序，有 90% 的人写出的程序中有各种各样的 Bug，读者不信的话可以不看书自己写一遍试试。这个算法容易出错的地方很多，比如 mid = (start + end) / 2; 这一句，在数学概念上其实是 mid = ⌊(start + end) / 2⌋ ，还有 start = mid + 1; 和 end = mid - 1; ，如果前者写成了 start = mid; 或后者写成了 end = mid; 那么很可能会导致死循环（想一想什么情况下会死循环）。

怎样才能保证程序的正确性呢？在 第 2 节“插入排序” 我们讲过借助 Loop Invariant 证明循环的正确性， binarysearch 这个函数的主体也是一个循环，它的 Loop Invariant 可以这样描述：待查找的元素 number 如果存在于数组 a 之中，那么一定存在于 a[start..end] 这个范围之间，换句话说，在这个范围之外的数组 a 的元素中一定不存在 number 这个元素。以下为了书写方便，我们把这句话表示成 mustbe(start, end, number) 。可以一边看算法一边做推理：

c
int binarysearch(int number) {
    int mid, start = 0, end = LEN - 1;

    /* 假定 a 是排好序的 */
    /* mustbe(start, end, number)，因为 a[start..end] 就是整个数组 a[0..LEN-1] */
    while (start <= end) {
        /* mustbe(start, end, number)，因为一开始进入循环时是正确的，每次循环也都维护了这个条件 */
        mid = (start + end) / 2;
        if (a[mid] < number)
            /* 既然 a 是排好序的，a[start..mid] 应该都比 number 小，所以 mustbe(mid+1, end, number) */
            start = mid + 1;
        /* 维护了 mustbe(start, end, number) */
        else if (a[mid] > number)
            /* 既然 a 是排好序的，a[mid..end] 应该都比 number 大，所以 mustbe(start, mid-1, number) */
            end = mid - 1;
        /* 维护了 mustbe(start, end, number) */
        else
            /* a[mid] == number，说明找到了 */
            return mid;
    }
    /*
     * mustbe(start, end, number) 一直被循环维护着，到这里应该仍然成立，在 a[start..end] 范围之外一定不存在 number，
     * 但现在 a[start..end] 是空序列，在这个范围之外的正是整个数组 a，因此整个数组 a 中都不存在 number */
    return -1;
}

注意这个算法有一个非常重要的前提－－ a 是排好序的。缺了这个前提，“如果 a[mid] < number ，那么 a[start..mid]应该都比 number 小”这一步推理就不能成立，这个函数就不能正确地完成查找。从更普遍的意义上说，函数的调用者（Caller）和函数的实现者（Callee，被调用者）之间订立了一个契约（Contract），在调用函数之前，Caller 要为 Callee 提供某些条件，比如确保 a 是排好序的，确保 a[start..end]都是有效的数组元素而没有访问越界，这称为 Precondition，然后 Callee 对一些 Invariant 进行维护（Maintenance），这些 Invariant 保证了 Callee 在函数返回时能够对 Caller 尽到某些义务，比如确保“如果 number 在数组 a 中存在，一定能找出来并返回它的位置，如果 number 在数组 a 中不存在，一定能返回 -1”，这称为 Postcondition。如果每个函数的文档都非常清楚地记录了 Precondition、Maintenance 和 Postcondition 是什么，那么每个函数都可以独立编写和测试，整个系统就会易于维护。这种编程思想是由 Eiffel 语言的设计者 Bertrand Meyer 提出来的，称为 Design by Contract（DbC）。

测试一个函数是否正确需要把 Precondition、Maintenance 和 Postcondition 这三方面都测试到，比如 binarysearch 这个函数，即使它写得非常正确，既维护了 Invariant 也保证了 Postcondition，如果调用它的 Caller 没有保证 Precondition，最后的结果也还是错的。我们编写几个测试用的 Predicate 函数，然后把相关的测试插入到 binarysearch 函数中：

例 11.5. 带有测试代码的折半查找

c
#include <assert.h>
#include <stdio.h>

#define LEN 8
int a[LEN] = {1, 2, 2, 2, 5, 6, 8, 9};

int is_sorted(void) {
    int i;
    for (i = 1; i < LEN; i++)
        if (a[i - 1] > a[i])
            return 0;
    return 1;
}

int mustbe(int start, int end, int number) {
    int i;
    for (i = 0; i < start; i++)
        if (a[i] == number)
            return 0;
    for (i = end + 1; i < LEN; i++)
        if (a[i] == number)
            return 0;
    return 1;
}

int contains(int n) {
    int i;
    for (i = 0; i < LEN; i++)
        if (a[i] == n)
            return 1;
    return 0;
}

int binarysearch(int number) {
    int mid, start = 0, end = LEN - 1;

    assert(is_sorted()); /* Precondition */
    while (start <= end) {
        assert(mustbe(start, end, number)); /* Maintenance */
        mid = (start + end) / 2;
        if (a[mid] < number)
            start = mid + 1;
        else if (a[mid] > number)
            end = mid - 1;
        else {
            assert(mid >= start && mid <= end &&
                   a[mid] == number) /* Postcondition 1 */
                return mid;
        }
    }
    assert(!contains(number)); /* Postcondition 2 */
    return -1;
}

int main(void) {
    printf("%d\n", binarysearch(5));
    return 0;
}

assert 是头文件 assert.h 中的一个宏定义，执行到 assert(is_sorted()) 这句时，如果 is_sorted() 返回值为真，则当什么事都没发生过，继续往下执行，如果 is_sorted() 返回值为假（例如把数组的排列顺序改一改），则报错退出程序：

bash
main: main.c:33: binarysearch: Assertion `is_sorted()' failed.
Aborted

在代码中适当的地方使用断言（Assertion）可以有效地帮助我们测试程序。也许有人会问：我们用几个测试函数来测试 binarysearch ，那么这几个测试函数又用什么来测试呢？在实际工作中我们要测试的代码绝不会像 binarysearch 这么简单，而我们编写的测试函数往往都很简单，比较容易保证正确性，也就是用简单的、不容易出错的代码去测试复杂的、容易出错的代码。

测试代码只在开发和调试时有用，如果正式发布（Release）的软件也要运行这些测试代码就会严重影响性能了，如果在包含 assert.h 之前定义一个 NDEBUG 宏（表示 No Debug），就可以禁用 assert.h 中的 assert 宏定义，这样代码中的所有 assert 测试都不起作用了：

c
#define NDEBUG
#include <stdio.h>
#include <assert.h>
...

注意 NDEBUG 和我们以前使用的宏定义有点不同，例如 #define N 20 将 N 定义为 20，在预处理时把代码中所有的标识符 N 替换成 20，而 #define NDEBUG 把 NDEBUG 定义为空，在预处理时把代码中所有的标识符 NDEBUG 替换成空。这样的宏定义主要是为了用 #ifdef 等预处理指示测试它定义过没有，而不是为了做替换，所以定义成什么值都无所谓，一般定义成空就足够了。

还有另一种办法，不必修改源文件，在编译命令行加上选项 -DNDEBUG 就相当于在源文件开头定义了 NDEBUG 宏。宏定义和预处理到 第 21 章 预处理再详细解释，在 第 4 节“其它预处理特性” 将给出 assert.h 一种实现。

习题 ​

  1. 本节的折半查找算法有一个特点：如果待查找的元素在数组中有多个则返回其中任意一个，以本节定义的数组 int a[8] = { 1, 2, 2, 2, 5, 6, 8, 9 }; 为例，如果调用 binarysearch(2) 则返回 3，即 a[3] ，而有些场合下要求这样的查找返回 a[1] ，也就是说，如果待查找的元素在数组中有多个则返回第一个。请修改折半查找算法实现这一特性。

  2. 编写一个函数 double mysqrt(double y); 求 y 的正平方根，参数 y 是正实数。我们用折半查找来找这个平方根，在从 0 到 y 之间必定有一个取值是 y 的平方根，如果我们查找的数 x 比 y 的平方根小，则 x2<y，如果我们查找的数 x 比 y 的平方根大，则 x2>y，我们可以据此缩小查找范围，当我们查找的数足够准确时（比如满足|x2-y|<0.001），就可以认为找到了 y 的平方根。思考一下这个算法需要迭代多少次？迭代次数的多少由什么因素决定？

  3. 编写一个函数 double mypow(double x, int n); 求 x 的 n 次方，参数 n 是正整数。最简单的算法是：

    c
    double product = 1;
for (i = 0; i < n; i++)
       product *= x;

    这个算法的时间复杂度是 Θ(n)。其实有更好的办法，比如 mypow(x, 8) ，第一次循环算出 x·x=x2，第二次循环算出 x2·x2=x4，第三次循环算出 x4·x4=x8。这样只需要三次循环，时间复杂度是 Θ(lgn)。思考一下如果 n 不是 2 的整数次幂应该怎么处理。请分别用递归和循环实现这个算法。

从以上几题可以看出，折半查找的思想有非常广泛的应用，不仅限于从一组排好序的元素中找出某个元素的位置，还可以解决很多类似的问题。编程珠玑 对于折半查找的各种应用和优化技巧有非常详细的介绍。