6. 折半查找 請(qǐng)點(diǎn)評(píng)如果不是從一組隨機(jī)的序列里查找，而是從一組排好序的序列里找出某個(gè)元素的位置，則可以有更快的算法： 例 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; } 由于這個(gè)序列已經(jīng)從小到大排好序了，每次取中間的元素和待查找的元素比較，如果中間的元素比待查找的元素小，就說明“如果待查找的元素存在，一定位于序列的后半部分”，這樣可以把搜索范圍縮小到后半部分，然后再次使用這種算法迭代。這種“每次將搜索范圍縮小一半”的思想稱為折半查找（Binary Search）。思考一下，這個(gè)算法的時(shí)間復(fù)雜度是多少？ 這個(gè)算法的思想很簡單，不是嗎？可是[編程珠璣]上說作者在課堂上講完這個(gè)算法的思想然后讓學(xué)生寫程序，有90%的人寫出的程序中有各種各樣的Bug，讀者不信的話可以不看書自己寫一遍試試。這個(gè)算法容易出錯(cuò)的地方很多，比如 怎樣才能保證程序的正確性呢？在第 2 節(jié) “插入排序”我們講過借助Loop Invariant證明循環(huán)的正確性，
注意這個(gè)算法有一個(gè)非常重要的前提－－ a是排好序的。缺了這個(gè)前提，“如果a[mid] < number，那么a[start..mid]應(yīng)該都比number小”這一步推理就不能成立，這個(gè)函數(shù)就不能正確地完成查找。從更普遍的意義上說，函數(shù)的調(diào)用者（Caller）和函數(shù)的實(shí)現(xiàn)者（Callee，被調(diào)用者）之間訂立了一個(gè)契約（Contract），在調(diào)用函數(shù)之前，Caller要為Callee提供某些條件，比如確保a是排好序的，確保a[start..end]都是有效的數(shù)組元素而沒有訪問越界，這稱為Precondition，然后Callee對(duì)一些Invariant進(jìn)行維護(hù)（Maintenance），這些Invariant保證了Callee在函數(shù)返回時(shí)能夠?qū)aller盡到某些義務(wù)，比如確保“如果number在數(shù)組a中存在，一定能找出來并返回它的位置，如果number在數(shù)組a中不存在，一定能返回-1”，這稱為Postcondition。如果每個(gè)函數(shù)的文檔都非常清楚地記錄了Precondition、Maintenance和Postcondition是什么，那么每個(gè)函數(shù)都可以獨(dú)立編寫和測試，整個(gè)系統(tǒng)就會(huì)易于維護(hù)。這種編程思想是由Eiffel語言的設(shè)計(jì)者Bertrand Meyer提出來的，稱為Design by Contract（DbC）。測試一個(gè)函數(shù)是否正確需要把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 在代碼中適當(dāng)?shù)牡胤绞褂脭嘌裕ˋssertion）可以有效地幫助我們測試程序。也許有人會(huì)問：我們用幾個(gè)測試函數(shù)來測試 測試代碼只在開發(fā)和調(diào)試時(shí)有用，如果正式發(fā)布（Release）的軟件也要運(yùn)行這些測試代碼就會(huì)嚴(yán)重影響性能了，如果在包含 #define NDEBUG #include <stdio.h> #include <assert.h> ... 注意 還有另一種辦法，不必修改源文件，在編譯命令行加上選項(xiàng) 習(xí)題 請(qǐng)點(diǎn)評(píng)1、本節(jié)的折半查找算法有一個(gè)特點(diǎn)：如果待查找的元素在數(shù)組中有多個(gè)則返回其中任意一個(gè)，以本節(jié)定義的數(shù)組 2、編寫一個(gè)函數(shù) 3、編寫一個(gè)函數(shù) double product = 1; for (i = 0; i < n; i++) product *= x; 這個(gè)算法的時(shí)間復(fù)雜度是Θ(n)。其實(shí)有更好的辦法，比如 從以上幾題可以看出，折半查找的思想有非常廣泛的應(yīng)用，不僅限于從一組排好序的元素中找出某個(gè)元素的位置，還可以解決很多類似的問題。[編程珠璣]對(duì)于折半查找的各種應(yīng)用和優(yōu)化技巧有非常詳細(xì)的介紹。 |
|
|
