6. 折半查找 请点评如果不是从一组随机的序列里查找,而是从一组排好序的序列里找出某个元素的位置,则可以有更快的算法: 例 11.4. 折半查找 #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,读者不信的话可以不看书自己写一遍试试。这个算法容易出错的地方很多,比如 怎样才能保证程序的正确性呢?在第 2 节 “插入排序”我们讲过借助Loop Invariant证明循环的正确性,
注意这个算法有一个非常重要的前提-- 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这三方面都测试到,比如 例 11.5. 带有测试代码的折半查找 #include <stdio.h> #include <assert.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; }
main: main.c:33: binarysearch: Assertion `is_sorted()' failed. Aborted 在代码中适当的地方使用断言(Assertion)可以有效地帮助我们测试程序。也许有人会问:我们用几个测试函数来测试 测试代码只在开发和调试时有用,如果正式发布(Release)的软件也要运行这些测试代码就会严重影响性能了,如果在包含 #define NDEBUG #include <stdio.h> #include <assert.h> ... 注意 还有另一种办法,不必修改源文件,在编译命令行加上选项 习题 请点评1、本节的折半查找算法有一个特点:如果待查找的元素在数组中有多个则返回其中任意一个,以本节定义的数组 2、编写一个函数 3、编写一个函数 double product = 1; for (i = 0; i < n; i++) product *= x; 这个算法的时间复杂度是Θ(n)。其实有更好的办法,比如 从以上几题可以看出,折半查找的思想有非常广泛的应用,不仅限于从一组排好序的元素中找出某个元素的位置,还可以解决很多类似的问题。[编程珠玑]对于折半查找的各种应用和优化技巧有非常详细的介绍。 |
|
来自: fruitapple > 《C语言》