# 第?11?章?排序與查找 **目錄** + [1\. 算法的概念](ch11s01.html) + [2\. 插入排序](ch11s02.html) + [3\. 算法的時間復雜度分析](ch11s03.html) + [4\. 歸并排序](ch11s04.html) + [5\. 線性查找](ch11s05.html) + [6\. 折半查找](ch11s06.html) ## 1.?算法的概念 算法（Algorithm）是將一組輸入轉化成一組輸出的一系列計算步驟，其中每個步驟必須能在有限時間內完成。比如[第?3?節 “遞歸”](ch05s03.html#func2.recursion)習題1中的Euclid算法，輸入是兩個正整數，輸出是它們的最大公約數，計算步驟是取模、比較等操作，這個算法一定能在有限的步驟和時間內完成（想一想為什么？）。再比如將一組數從小到大排序，輸入是一組原始數據，輸出是排序之后的數據，計算步驟包括比較、移動數據等操作。 算法是用來解決一類計算問題的，注意是一類問題，而不是一個特定的問題。例如，一個排序算法應該能對任意一組數據進行排序，而不是僅對`int a[] = { 1, 3, 4, 2, 6, 5 };`這樣一組數據排序，如果只需要對這一組數據排序可以寫這樣一個函數來做： ``` void sort(void) { a[0] = 1; a[1] = 2; a[2] = 3; a[3] = 4; a[4] = 5; a[5] = 6; } ``` 這顯然不叫算法，因為不具有通用性。由于算法是用來解決一類問題的，它必須能夠正確地解決這一類問題中的任何一個實例，這個算法才是正確的。對于排序算法，任意輸入一組數據，它必須都能輸出正確的排序結果，這個排序算法才是正確的。不正確的算法有兩種可能，一是對于該問題的某些輸入，該算法會無限計算下去，不會終止，二是對于該問題的某些輸入，該算法終止時輸出的是錯誤的結果。有時候不正確的算法也是有用的，如果對于某個問題尋求正確的算法很困難，而某個不正確的算法可以在有限時間內終止，并且能把誤差控制在一定范圍內，那么這樣的算法也是有實際意義的。例如有時候尋找最優解的開銷很大，往往會選擇能給出次優解的算法。 本章介紹幾種典型的排序和查找算法，并圍繞這幾種算法做時間復雜度分析。學完本章之后如果想進一步學習，可以參考一些全面系統地介紹算法的書，例如[[TAOCP]](bi01.html#bibli.taocp "The Art of Computer Programming")和[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")。 ## 2.?插入排序 插入排序算法類似于玩撲克時抓牌的過程，玩家每拿到一張牌都要插入到手中已有的牌里，使之從小到大排好序。例如（該圖出自[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")）： **圖?11.1.?撲克牌的插入排序**  也許你沒有意識到，但其實你的思考過程是這樣的：現在抓到一張7，把它和手里的牌從右到左依次比較，7比10小，應該再往左插，7比5大，好，就插這里。為什么比較了10和5就可以確定7的位置？為什么不用再比較左邊的4和2呢？因為這里有一個重要的前提：手里的牌已經是排好序的。現在我插了7之后，手里的牌仍然是排好序的，下次再抓到的牌還可以用這個方法插入。 編程對一個數組進行插入排序也是同樣道理，但和插入撲克牌有一點不同，不可能在兩個相鄰的存儲單元之間再插入一個單元，因此要將插入點之后的數據依次往后移動一個單元。排序算法如下： **例?11.1.?插入排序** ``` #include <stdio.h> #define LEN 5 int a[LEN] = { 10, 5, 2, 4, 7 }; void insertion_sort(void) { int i, j, key; for (j = 1; j < LEN; j++) { printf("%d, %d, %d, %d, %d\n", a[0], a[1], a[2], a[3], a[4]); key = a[j]; i = j - 1; while (i >= 0 && a[i] > key) { a[i+1] = a[i]; i--; } a[i+1] = key; } printf("%d, %d, %d, %d, %d\n", a[0], a[1], a[2], a[3], a[4]); } int main(void) { insertion_sort(); return 0; } ``` 為了更清楚地觀察排序過程，我們在每次循環開頭插了打印語句，在排序結束后也插了打印語句。程序運行結果是： ``` _10_, 5, 2, 4, 7 _5, 10_, 2, 4, 7 _2, 5, 10_, 4, 7 _2, 4, 5, 10_, 7 _2, 4, 5, 7, 10_ ``` 如何嚴格證明這個算法是正確的？換句話說，只要反復執行該算法的`for`循環體，執行`LEN-1`次，就一定能把數組`a`排好序，而不管數組`a`的原始數據是什么，如何證明這一點呢？我們可以借助Loop Invariant的概念和數學歸納法來理解循環結構的算法，假如某個判斷條件滿足以下三條準則，它就稱為Loop Invariant： 1. 第一次執行循環體之前該判斷條件為真。 2. 如果“第N-1次循環之后（或者說第N次循環之前）該判斷條件為真”這個前提可以成立，那么就有辦法證明第N次循環之后該判斷條件仍為真。 3. 如果在所有循環結束后該判斷條件為真，那么就有辦法證明該算法正確地解決了問題。 只要我們找到這個Loop Invariant，就可以證明一個循環結構的算法是正確的。上述插入排序算法的Loop Invariant是這樣的判斷條件：_第`j`次循環之前，子序列a[0..j-1]是排好序的_。在上面的打印結果中，我把子序列a[0..j-1]加粗表示。下面我們驗證一下Loop Invariant的三條準則： 1. 第一次執行循環之前，`j=1`，子序列a[0..j-1]只有一個元素`a[0]`，只有一個元素的序列顯然是排好序的。 2. 第`j`次循環之前，如果“子序列a[0..j-1]是排好序的”這個前提成立，現在要把`key=a[j]`插進去，按照該算法的步驟，把`a[j-1]`、`a[j-2]`、`a[j-3]`等等比`key`大的元素都依次往后移一個，直到找到合適的位置給`key`插入，就能證明循環結束時子序列a[0..j]是排好序的。就像插撲克牌一樣，“手中已有的牌是排好序的”這個前提很重要，如果沒有這個前提，就不能證明再插一張牌之后也是排好序的。 3. 當循環結束時，`j=LEN`，如果“子序列a[0..j-1]是排好序的”這個前提成立，那就是說a[0..LEN-1]是排好序的，也就是說整個數組`a`的`LEN`個元素都排好序了。 可見，有了這三條，就可以用數學歸納法證明這個循環是正確的。這和[第?3?節 “遞歸”](ch05s03.html#func2.recursion)證明遞歸程序正確性的思想是一致的，這里的第一條就相當于遞歸的Base Case，第二條就相當于遞歸的遞推關系。這再次說明了遞歸和循環是等價的。 ## 3.?算法的時間復雜度分析 解決同一個問題可以有很多種算法，比較評價算法的好壞，一個重要的標準就是算法的時間復雜度。現在研究一下插入排序算法的執行時間，按照習慣，輸入長度`LEN`以下用n表示。設循環中各條語句的執行時間分別是c1、c2、c3、c4、c5這樣五個常數^{[[23](#ftn.id2745592)]}： ``` void insertion_sort(void) 執行時間 { int i, j, key; for (j = 1; j < LEN; j++) { key = a[j]; c1 i = j - 1; c2 while (i >= 0 && a[i] > key) { a[i+1] = a[i]; c3 i--; c4 } a[i+1] = key; c5 } } ``` 顯然外層`for`循環的執行次數是n-1次，假設內層的`while`循環執行m次，則總的執行時間粗略估計是(n-1)*(c1+c2+c5+m*(c3+c4))。當然，`for`和`while`后面()括號中的賦值和條件判斷的執行也需要時間，而我沒有設一個常數來表示，這不影響我們的粗略估計。 這里有一個問題，m不是個常數，也不取決于輸入長度n，而是取決于具體的輸入數據。在最好情況下，數組`a`的原始數據已經排好序了，`while`循環一次也不執行，總的執行時間是(c1+c2+c5)*n-(c1+c2+c5)，可以表示成an+b的形式，是n的線性函數（Linear Function）。那么在最壞情況（Worst Case）下又如何呢？所謂最壞情況是指數組`a`的原始數據正好是從大到小排好序的，請讀者想一想為什么這是最壞情況，然后把上式中的m替換掉算一下執行時間是多少。 數組`a`的原始數據屬于最好和最壞情況的都比較少見，如果原始數據是隨機的，可稱為平均情況（Average Case）。如果原始數據是隨機的，那么每次循環將已排序的子序列a[1..j-1]與新插入的元素`key`相比較，子序列中平均都有一半的元素比`key`大而另一半比`key`小，請讀者把上式中的m替換掉算一下執行時間是多少。最后的結論應該是：在最壞情況和平均情況下，總的執行時間都可以表示成an²+bn+c的形式，是n的二次函數（Quadratic Function）。 在分析算法的時間復雜度時，我們更關心最壞情況而不是最好情況，理由如下： 1. 最壞情況給出了算法執行時間的上界，我們可以確信，無論給什么輸入，算法的執行時間都不會超過這個上界，這樣為比較和分析提供了便利。 2. 對于某些算法，最壞情況是最常發生的情況，例如在數據庫中查找某個信息的算法，最壞情況就是數據庫中根本不存在該信息，都找遍了也沒有，而某些應用場合經常要查找一個信息在數據庫中存在不存在。 3. 雖然最壞情況是一種悲觀估計，但是對于很多問題，平均情況和最壞情況的時間復雜度差不多，比如插入排序這個例子，平均情況和最壞情況的時間復雜度都是輸入長度n的二次函數。 比較兩個多項式a₁n+b₁和a₂n²+b₂n+c₂的值（n取正整數）可以得出結論：n的最高次指數是最主要的決定因素，常數項、低次冪項和系數都是次要的。比如100n+1和n²+1，雖然后者的系數小，當n較小時前者的值較大，但是當n&gt;100時，后者的值就遠遠大于前者了。如果同一個問題可以用兩種算法解決，其中一種算法的時間復雜度為線性函數，另一種算法的時間復雜度為二次函數，當問題的輸入長度n足夠大時，前者明顯優于后者。因此我們可以用一種更粗略的方式表示算法的時間復雜度，把系數和低次冪項都省去，線性函數記作Θ(n)，二次函數記作Θ(n²)。 Θ(g(n))表示和g(n)同一量級的一類函數，例如所有的二次函數f(n)都和g(n)=n²屬于同一量級，都可以用Θ(n²)來表示，甚至有些不是二次函數的也和n²屬于同一量級，例如2n²+3lgn。“同一量級”這個概念可以用下圖來說明（該圖出自[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")）： **圖?11.2.?Θ-notation**  如果可以找到兩個正的常數c₁和c₂，使得n足夠大的時候（也就是n≥n₀的時候）f(n)總是夾在c₁g(n)和c₂g(n)之間，就說f(n)和g(n)是同一量級的，f(n)就可以用Θ(g(n))來表示。 以二次函數為例，比如1/2n²-3n，要證明它是屬于Θ(n²)這個集合的，我們必須確定c₁、c₂和n₀，這些常數不隨n改變，并且當n≥n₀以后，c₁n²≤1/2n²-3n≤c₂n²總是成立的。為此我們從不等式的每一邊都除以n²，得到c₁≤1/2-3/n≤c₂。見下圖： **圖?11.3.?1/2-3/n**  這樣就很容易看出來，無論n取多少，該函數一定小于1/2，因此c₂=1/2，當n=6時函數值為0，n&gt;6時該函數都大于0，可以取n₀=7，c₁=1/14，這樣當n≥n₀時都有1/2-3/n≥c₁。通過這個證明過程可以得出結論，當n足夠大時任何an²+bn+c都夾在c₁n²和c₂n²之間，相對于n²項來說bn+c的影響可以忽略，a可以通過選取合適的c₁、c₂來補償。 幾種常見的時間復雜度函數按數量級從小到大的順序依次是：Θ(lgn)，Θ(sqrt(n))，Θ(n)，Θ(nlgn)，Θ(n²)，Θ(n³)，Θ(2ⁿ)，Θ(n!)。其中，lgn通常表示以10為底n的對數，但是對于Θ-notation來說，Θ(lgn)和Θ(log₂n)并無區別（想一想這是為什么），在算法分析中lgn通常表示以2為底n的對數。可是什么算法的時間復雜度里會出現lgn呢？回顧插入排序的時間復雜度分析，無非是循環體的執行時間乘以循環次數，只有加和乘運算，怎么會出來lg呢？下一節歸并排序的時間復雜度里面就有lg，請讀者留心lg運算是從哪出來的。 除了Θ-notation之外，表示算法的時間復雜度常用的還有一種Big-O notation。我們知道插入排序在最壞情況和平均情況下時間復雜度是Θ(n²)，在最好情況下是Θ(n)，數量級比Θ(n²)要小，那么總結起來在各種情況下插入排序的時間復雜度是O(n²)。Θ的含義和“等于”類似，而大O的含義和“小于等于”類似。 * * * ^{[[23](#id2745592)]} 受內存管理機制的影響，指令的執行時間不一定是常數，但執行時間的上界（Upper Bound）肯定是常數，我們這里假設語句的執行時間是常數只是一個粗略估計。 ## 4.?歸并排序 插入排序算法采取增量式（Incremental）的策略解決問題，每次添一個元素到已排序的子序列中，逐漸將整個數組排序完畢，它的時間復雜度是O(n²)。下面介紹另一種典型的排序算法－－歸并排序，它采取分而治之（Divide-and-Conquer）的策略，時間復雜度是Θ(nlgn)。歸并排序的步驟如下： 1. Divide: 把長度為n的輸入序列分成兩個長度為n/2的子序列。 2. Conquer: 對這兩個子序列分別采用歸并排序。 3. Combine: 將兩個排序好的子序列合并成一個最終的排序序列。 在描述歸并排序的步驟時又調用了歸并排序本身，可見這是一個遞歸的過程。 **例?11.2.?歸并排序** ``` #include <stdio.h> #define LEN 8 int a[LEN] = { 5, 2, 4, 7, 1, 3, 2, 6 }; void merge(int start, int mid, int end) { int n1 = mid - start + 1; int n2 = end - mid; int left[n1], right[n2]; int i, j, k; for (i = 0; i < n1; i++) /* left holds a[start..mid] */ left[i] = a[start+i]; for (j = 0; j < n2; j++) /* right holds a[mid+1..end] */ right[j] = a[mid+1+j]; i = j = 0; k = start; while (i < n1 && j < n2) if (left[i] < right[j]) a[k++] = left[i++]; else a[k++] = right[j++]; while (i < n1) /* left[] is not exhausted */ a[k++] = left[i++]; while (j < n2) /* right[] is not exhausted */ a[k++] = right[j++]; } void sort(int start, int end) { int mid; if (start < end) { mid = (start + end) / 2; printf("sort (%d-%d, %d-%d) %d %d %d %d %d %d %d %d\n", start, mid, mid+1, end, a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]); sort(start, mid); sort(mid+1, end); merge(start, mid, end); printf("merge (%d-%d, %d-%d) to %d %d %d %d %d %d %d %d\n", start, mid, mid+1, end, a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]); } } int main(void) { sort(0, LEN-1); return 0; } ``` 執行結果是： ``` sort (0-3, 4-7) 5 2 4 7 1 3 2 6 sort (0-1, 2-3) 5 2 4 7 1 3 2 6 sort (0-0, 1-1) 5 2 4 7 1 3 2 6 merge (0-0, 1-1) to 2 5 4 7 1 3 2 6 sort (2-2, 3-3) 2 5 4 7 1 3 2 6 merge (2-2, 3-3) to 2 5 4 7 1 3 2 6 merge 0-1, 2-3) to 2 4 5 7 1 3 2 6 sort (4-5, 6-7) 2 4 5 7 1 3 2 6 sort (4-4, 5-5) 2 4 5 7 1 3 2 6 merge (4-4, 5-5) to 2 4 5 7 1 3 2 6 sort (6-6, 7-7) 2 4 5 7 1 3 2 6 merge (6-6, 7-7) to 2 4 5 7 1 3 2 6 merge (4-5, 6-7) to 2 4 5 7 1 2 3 6 merge (0-3, 4-7) to 1 2 2 3 4 5 6 7 ``` `sort`函數把a[start..end]平均分成兩個子序列，分別是a[start..mid]和a[mid+1..end]，對這兩個子序列分別遞歸調用`sort`函數進行排序，然后調用`merge`函數將排好序的兩個子序列合并起來，由于兩個子序列都已經排好序了，合并的過程很簡單，每次循環取兩個子序列中最小的元素進行比較，將較小的元素取出放到最終的排序序列中，如果其中一個子序列的元素已取完，就把另一個子序列剩下的元素都放到最終的排序序列中。為了便于理解程序，我在`sort`函數開頭和結尾插了打印語句，可以看出調用過程是這樣的： **圖?11.4.?歸并排序調用過程**  圖中S表示`sort`函數，M表示`merge`函數，整個控制流程沿虛線所示的方向調用和返回。由于`sort`函數遞歸調用了自己兩次，所以各函數之間的調用關系呈樹狀結構。畫這個圖只是為了清楚地展現歸并排序的過程，讀者在理解遞歸函數時一定不要全部展開來看，而是要抓住Base Case和遞推關系來理解。我們分析一下歸并排序的時間復雜度，以下分析出自[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")。 首先分析`merge`函數的時間復雜度。在`merge`函數中演示了C99的新特性－－可變長數組，當然也可以避免使用這一特性，比如把`left`和`right`都按最大長度`LEN`分配。不管用哪種辦法，定義數組并分配存儲空間的執行時間都可以看作常數，與數組的長度無關，常數用Θ-notation記作Θ(1)。設子序列a[start..mid]的長度為`n1`，子序列[mid+1..end]的長度為`n2`，a[start..end]的總長度為n=n1+n2，則前兩個`for`循環的執行時間是Θ(n1+n2)，也就是Θ(n)，后面三個`for`循環合在一起看，每走一次循環就會在最終的排序序列中確定一個元素，最終的排序序列共有n個元素，所以執行時間也是Θ(n)。兩個Θ(n)再加上若干常數項，`merge`函數總的執行時間仍是Θ(n)，其中n=end-start+1。 然后分析`sort`函數的時間復雜度，當輸入長度n=1，也就是`start==end`時，`if`條件不成立，執行時間為常數Θ(1)，當輸入長度n&gt;1時： 總的執行時間?=?2?×?輸入長度為n/2的`sort`函數的執行時間?+?`merge`函數的執行時間Θ(n) 設輸入長度為n的`sort`函數的執行時間為T(n)，綜上所述：  這是一個遞推公式（Recurrence），我們需要消去等號右側的T(n)，把T(n)寫成n的函數。其實符合一定條件的Recurrence的展開有數學公式可以套，這里我們略去嚴格的數學證明，只是從直觀上看一下這個遞推公式的結果。當n=1時可以設T(1)=c₁，當n&gt;1時可以設T(n)=2T(n/2)+c₂n，我們取c₁和c₂中較大的一個設為c，把原來的公式改為：  這樣計算出的結果應該是T(n)的上界。下面我們把T(n/2)展開成2T(n/4)+cn/2（下圖中的(c)），然后再把T(n/4)進一步展開，直到最后全部變成T(1)=c（下圖中的(d)）：  把圖(d)中所有的項加起來就是總的執行時間。這是一個樹狀結構，每一層的和都是cn，共有lgn+1層，因此總的執行時間是cnlgn+cn，相比nlgn來說，cn項可以忽略，因此T(n)的上界是Θ(nlgn)。 如果先前取c₁和c₂中較小的一個設為c，計算出的結果應該是T(n)的下界，然而推導過程一樣，結果也是Θ(nlgn)。既然T(n)的上下界都是Θ(nlgn)，顯然T(n)就是Θ(nlgn)。 和插入排序的平均情況相比歸并排序更快一些，雖然`merge`函數的步驟較多，引入了較大的常數、系數和低次項，但是對于較大的輸入長度n，這些都不是主要因素，歸并排序的時間復雜度是Θ(nlgn)，而插入排序的平均情況是Θ(n²)，這就決定了歸并排序是更快的算法。但是不是任何情況下歸并排序都優于插入排序呢？哪些情況適用插入排序而不適用歸并排序？留給讀者思考。 ### 習題 1、快速排序是另外一種采用分而治之策略的排序算法，在平均情況下的時間復雜度也是Θ(nlgn)，但比歸并排序有更小的時間常數。它的基本思想是這樣的： ``` int partition(int start, int end) { 從a[start..end]中選取一個pivot元素（比如選a[start]為pivot）; 在一個循環中移動a[start..end]的數據，將a[start..end]分成兩半， 使a[start..mid-1]比pivot元素小，a[mid+1..end]比pivot元素大，而a[mid]就是pivot元素; return mid; } void quicksort(int start, int end) { int mid; if (end > start) { mid = partition(start, end); quicksort(start, mid-1); quicksort(mid+1, end); } } ``` 請補完`partition`函數，這個函數有多種寫法，請選擇時間常數盡可能小的實現方法。想想快速排序在最好和最壞情況下的時間復雜度是多少？快速排序在平均情況下的時間復雜度分析起來比較復雜，有興趣的讀者可以參考[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")。 ## 5.?線性查找 有些查找問題要用時間復雜度為O(n)的算法來解決。例如寫一個`indexof`函數，從任意輸入字符串中找出某個字母的位置并返回這個位置，如果找不到就返回-1： **例?11.3.?線性查找** ``` #include <stdio.h> char a[]="hello world"; int indexof(char letter) { int i = 0; while (a[i] != '\0') { if (a[i] == letter) return i; i++; } return -1; } int main(void) { printf("%d %d\n", indexof('o'), indexof('z')); return 0; } ``` 這個實現是最直觀和最容易想到的，但它是不是最快的算法呢？我們知道插入排序也比歸并排序更容易想到，但通常不如歸并排序快。那么現在這個問題－－給定一個隨機排列的序列，找出其中某個元素的位置－－有沒有比O(n)更快的算法？比如O(lgn)？請讀者思考一下。 ### 習題 1、實現一個算法，在一組隨機排列的數中找出最小的一個。你能想到的最直觀的算法一定是Θ(n)的，想想有沒有比Θ(n)更快的算法？ 2、在一組隨機排列的數中找出第二小的，這個問題比上一個稍復雜，你能不能想出Θ(n)的算法？ 3、進一步泛化，在一組隨機排列的數中找出第k小的，這個元素稱為k-th Order Statistic。能想到的最直觀的算法肯定是先把這些數排序然后取第k個，時間復雜度和排序算法相同，可以是Θ(nlgn)。這個問題雖然比前兩個問題復雜，但它也有平均情況下時間復雜度是Θ(n)的算法，將上一節習題1的快速排序算法稍加修改就可以解決這個問題： ``` /* 從start到end之間找出第k小的元素 */ int order_statistic(int start, int end, int k) { 用partition函數把序列分成兩半，中間的pivot元素是序列中的第i個; if (k == i) 返回找到的元素; else if (k > i) 從后半部分找出第k-i小的元素并返回; else 從前半部分找出第k小的元素并返回; } ``` 請編程實現這個算法。 ## 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）。思考一下，這個算法的時間復雜度是多少？ 這個算法的思想很簡單，不是嗎？可是[[編程珠璣]](bi01.html#bibli.pearls "Programming Pearls")上說作者在課堂上講完這個算法的思想然后讓學生寫程序，有90%的人寫出的程序中有各種各樣的Bug，讀者不信的話可以不看書自己寫一遍試試。這個算法容易出錯的地方很多，比如`mid = (start + end) / 2;`這一句，在數學概念上其實是`mid = ?(start + end) / 2?`，還有`start = mid + 1;`和`end = mid - 1;`，如果前者寫成了`start = mid;`或后者寫成了`end = mid;`那么很可能會導致死循環（想一想什么情況下會死循環）。 怎樣才能保證程序的正確性呢？在[第?2?節 “插入排序”](ch11s02.html#sortsearch.insertion)我們講過借助Loop Invariant證明循環的正確性，`binarysearch`這個函數的主體也是一個循環，它的Loop Invariant可以這樣描述：_待查找的元素`number`如果存在于數組`a`之中，那么一定存在于a[start..end]這個范圍之間，換句話說，在這個范圍之外的數組`a`的元素中一定不存在`number`這個元素_。以下為了書寫方便，我們把這句話表示成`mustbe(start, end, number)`。可以一邊看算法一邊做推理： ``` 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] &lt; 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.?帶有測試代碼的折半查找** ``` #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; } ``` `assert`是頭文件`assert.h`中的一個宏定義，執行到`assert(is_sorted())`這句時，如果`is_sorted()`返回值為真，則當什么事都沒發生過，繼續往下執行，如果`is_sorted()`返回值為假（例如把數組的排列順序改一改），則報錯退出程序： ``` main: main.c:33: binarysearch: Assertion `is_sorted()' failed. Aborted ``` 在代碼中適當的地方使用斷言（Assertion）可以有效地幫助我們測試程序。也許有人會問：我們用幾個測試函數來測試`binarysearch`，那么這幾個測試函數又用什么來測試呢？在實際工作中我們要測試的代碼絕不會像`binarysearch`這么簡單，而我們編寫的測試函數往往都很簡單，比較容易保證正確性，也就是用簡單的、不容易出錯的代碼去測試復雜的、容易出錯的代碼。 測試代碼只在開發和調試時有用，如果正式發布（Release）的軟件也要運行這些測試代碼就會嚴重影響性能了，如果在包含`assert.h`之前定義一個`NDEBUG`宏（表示No Debug），就可以禁用`assert.h`中的`assert`宏定義，這樣代碼中的所有`assert`測試都不起作用了： ``` #define NDEBUG #include <stdio.h> #include <assert.h> ... ``` 注意`NDEBUG`和我們以前使用的宏定義有點不同，例如`#define N 20`將`N`定義為20，在預處理時把代碼中所有的標識符`N`替換成20，而`#define NDEBUG`把`NDEBUG`定義為空，在預處理時把代碼中所有的標識符`NDEBUG`替換成空。這樣的宏定義主要是為了用`#ifdef`等預處理指示測試它定義過沒有，而不是為了做替換，所以定義成什么值都無所謂，一般定義成空就足夠了。 還有另一種辦法，不必修改源文件，在編譯命令行加上選項`-DNDEBUG`就相當于在源文件開頭定義了`NDEBUG`宏。宏定義和預處理到[第?21?章 _預處理_](ch21.html#prep)再詳細解釋，在[第?4?節 “其它預處理特性”](ch21s04.html#prep.other)將給出`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`的平方根小，則x²&lt;y，如果我們查找的數`x`比`y`的平方根大，則x²&gt;y，我們可以據此縮小查找范圍，當我們查找的數足夠準確時（比如滿足|x²-y|&lt;0.001），就可以認為找到了`y`的平方根。思考一下這個算法需要迭代多少次？迭代次數的多少由什么因素決定？ 3、編寫一個函數`double mypow(double x, int n);`求`x`的`n`次方，參數`n`是正整數。最簡單的算法是： ``` double product = 1; for (i = 0; i < n; i++) product *= x; ``` 這個算法的時間復雜度是Θ(n)。其實有更好的辦法，比如`mypow(x, 8)`，第一次循環算出x·x=x²，第二次循環算出x²·x²=x⁴，第三次循環算出⁴·x⁴=x⁸。這樣只需要三次循環，時間復雜度是Θ(lgn)。思考一下如果`n`不是2的整數次冪應該怎么處理。請分別用遞歸和循環實現這個算法。 從以上幾題可以看出，折半查找的思想有非常廣泛的應用，不僅限于從一組排好序的元素中找出某個元素的位置，還可以解決很多類似的問題。[[編程珠璣]](bi01.html#bibli.pearls "Programming Pearls")對于折半查找的各種應用和優化技巧有非常詳細的介紹。