例 11.4. 折半查找

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

    这个算法的思想很简单，不是吗？可是上说作者在课堂上讲完这个算法的思想然后让学生写程序，有90%的人写出的程序中有各种各样的Bug，读者不信的话可以不看书自己写一遍试试。这个算法容易出错的地方很多，比如这一句，在数学概念上其实是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)。可以一边看算法一边做推理：

    1. int binarysearch(int number)
    2. {
    3.     int mid, start = 0, end = LEN - 1;
    4.  
    5.     /* 假定a是排好序的 */
    6.     /* mustbe(start, end, number)，因为a[start..end]就是整个数组a[0..LEN-1] */
    7.     while (start <= end) {
    8.     /* mustbe(start, end, number)，因为一开始进入循环时是正确的，每次循环也都维护了这个条件 */
    9.         mid = (start + end) / 2;
    10.             /* 既然a是排好序的，a[start..mid]应该都比number小，所以mustbe(mid+1, end, number) */
    11.             start = mid + 1;
    12.             /* 维护了mustbe(start, end, number) */
    13.         else if (a[mid] > number)
    14.             /* 既然a是排好序的，a[mid..end]应该都比number大，所以mustbe(start, mid-1, number) */
    15.             end = mid - 1;
    16.             /* 维护了mustbe(start, end, number) */
    17.         else
    18.             /* a[mid] == number，说明找到了 */
    19.             return mid;
    20.     /* 
    21.      * mustbe(start, end, number)一直被循环维护着，到这里应该仍然成立，在a[start..end]范围之外一定不存在number，
    22.      * 但现在a[start..end]是空序列，在这个范围之外的正是整个数组a，因此整个数组a中都不存在number
    23.      */
    24.     return -1;
    25. }

    注意这个算法有一个非常重要的前提－－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）。

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

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

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

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

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

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

    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的平方根小，则x2y，我们可以据此缩小查找范围，当我们查找的数足够准确时（比如满足|x2-y|<0.001），就可以认为找到了y的平方根。思考一下这个算法需要迭代多少次？迭代次数的多少由什么因素决定？

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

    1. double product = 1;
    2. for (i = 0; i < n; i++)

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

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