6. 折半查找

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

例 11.4. 折半查找

  1. #include <stdio.h>
  2.  
  3. #define LEN 8
  4. int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };
  5.  
  6. int binarysearch(int number)
  7. {
  8. int mid, start = 0, end = LEN - 1;
  9.  
  10. while (start <= end) {
  11. mid = (start + end) / 2;
  12. if (a[mid] < number)
  13. start = mid + 1;
  14. else if (a[mid] > number)
  15. end = mid - 1;
  16. else
  17. return mid;
  18. }
  19. return -1;
  20. }
  21.  
  22. int main(void)
  23. {
  24. printf("%d\n", binarysearch(5));
  25. return 0;
  26. }

由于这个序列已经从小到大排好序了,每次取中间的元素和待查找的元素比较,如果中间的元素比待查找的元素小,就说明“如果待查找的元素存在,一定位于序列的后半部分”,这样可以把搜索范围缩小到后半部分,然后再次使用这种算法迭代。这种“每次将搜索范围缩小一半”的思想称为折半查找(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)。可以一边看算法一边做推理:

  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. if (a[mid] < number)
  11. /* 既然a是排好序的,a[start..mid]应该都比number小,所以mustbe(mid+1, end, number) */
  12. start = mid + 1;
  13. /* 维护了mustbe(start, end, number) */
  14. else if (a[mid] > number)
  15. /* 既然a是排好序的,a[mid..end]应该都比number大,所以mustbe(start, mid-1, number) */
  16. end = mid - 1;
  17. /* 维护了mustbe(start, end, number) */
  18. else
  19. /* a[mid] == number,说明找到了 */
  20. return mid;
  21. }
  22. /*
  23. * mustbe(start, end, number)一直被循环维护着,到这里应该仍然成立,在a[start..end]范围之外一定不存在number,
  24. * 但现在a[start..end]是空序列,在这个范围之外的正是整个数组a,因此整个数组a中都不存在number
  25. */
  26. return -1;
  27. }

注意这个算法有一个非常重要的前提--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. 带有测试代码的折半查找

  1. #include <stdio.h>
  2. #include <assert.h>
  3.  
  4. #define LEN 8
  5. int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };
  6.  
  7. int is_sorted(void)
  8. {
  9. int i;
  10. for (i = 1; i < LEN; i++)
  11. if (a[i-1] > a[i])
  12. return 0;
  13. return 1;
  14. }
  15.  
  16. int mustbe(int start, int end, int number)
  17. {
  18. int i;
  19. for (i = 0; i < start; i++)
  20. if (a[i] == number)
  21. return 0;
  22. for (i = end+1; i < LEN; i++)
  23. if (a[i] == number)
  24. return 0;
  25. return 1;
  26. }
  27.  
  28. int contains(int n)
  29. {
  30. int i;
  31. for (i = 0; i < LEN; i++)
  32. if (a[i] == n)
  33. return 1;
  34. return 0;
  35. }
  36.  
  37. int binarysearch(int number)
  38. {
  39. int mid, start = 0, end = LEN - 1;
  40.  
  41. assert(is_sorted()); /* Precondition */
  42. while (start <= end) {
  43. assert(mustbe(start, end, number)); /* Maintenance */
  44. mid = (start + end) / 2;
  45. if (a[mid] < number)
  46. start = mid + 1;
  47. else if (a[mid] > number)
  48. end = mid - 1;
  49. else {
  50. assert(mid >= start && mid <= end
  51. && a[mid] == number) /* Postcondition 1 */
  52. return mid;
  53. }
  54. }
  55. assert(!contains(number)); /* Postcondition 2 */
  56. return -1;
  57. }
  58.  
  59. int main(void)
  60. {
  61. printf("%d\n", binarysearch(5));
  62. return 0;
  63. }

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测试都不起作用了:

  1. #define NDEBUG
  2. #include <stdio.h>
  3. #include <assert.h>
  4. ...

注意NDEBUG和我们以前使用的宏定义有点不同,例如#define N 20N定义为20,在预处理时把代码中所有的标识符N替换成20,而#define NDEBUGNDEBUG定义为空,在预处理时把代码中所有的标识符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的平方根,如果我们查找的数xy的平方根小,则x2y,我们可以据此缩小查找范围,当我们查找的数足够准确时(比如满足|x2-y|<0.001),就可以认为找到了y的平方根。思考一下这个算法需要迭代多少次?迭代次数的多少由什么因素决定?

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

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

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

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