如果牌堆中的紙牌不是按順序排列的，那就沒有比線性查找更快的查找方法了。我們必須查看每張紙牌，因為除此之外我們無法確定要找的紙牌是不是在其中。 但是查詞典時，我們并不是從頭到尾、一個詞一個詞的查。因為單詞是以字母順序排列的，所以我們可以使用類似于二分查找的算法： 1. 從中間某個位置開始。 2. 在這一頁上選擇一個單詞，并用這個單詞和我們要查找的單詞比較。 3. 如果這就是我們要找的單詞，結束。 4. 如果我們要找的單詞在這一頁上的單詞之后，翻到后面某頁并回到第2步。 5. 如果我們要找的單詞在這一頁上的單詞之前，翻到詞典前面某頁并回到第2步。 如果遇到了這種情況，某頁上有兩個相鄰的單詞，而要找的單詞應該在它們之間，這時即可確定詞典中沒要我們要查的單詞。唯一的例外就是單詞印錯地方了，但這就與單詞按字母順序排列的假設沖突了。 在牌堆這個例子中，如果知道紙牌是有序擺放的，我們就能寫一個更快的find函數。編寫二分查找最好的方法是利用遞歸函數，因為二分自然而然是遞歸的。 竅門是編寫findBisect函數，它以兩個索引值low和high為參數，用以確定要查找的向量的一段（包括low和high指定的元素）。 1. 要在向量中查找，選擇low和high之間的一個索引，我們稱之為mid。將mid指定的紙牌與我們要查找的牌相比。 2. 如果找到，結束。 3. 如果mid處的紙牌比要找的牌大，繼續在low和mid-1確定的區間中查找。 4. 如果mid處的紙牌比要找的牌小，繼續在mid+1和high確定的區間中查找。 可以懷疑第3步和第4步看起來像遞歸調用。我們將其轉化為C++代碼，看起來是這個樣子的： ~~~ int findBisect (const Card& card, const apvector<Card>& deck, int low, int high) { int mid = (high + low) / 2; // 如果找到了紙牌，返回其index if (equals (deck[mid], card)) return mid; // 否則，將紙牌與中間的紙牌比較 if (deck[mid].isGreater (card)) { // 查找紙牌的前一半 return findBisect (card, deck, low, mid-1); } else { // 查找紙牌的后一半 return findBisect (card, deck, mid+1, high); } } ~~~ 雖然這段代碼已經包含了二分查找的核心，但還是缺點什么。按照當前代碼，如果要找的紙牌不再牌堆中，它會一直遞歸下去。我們需要找到一種方法來檢查這一條件并做出適當的處理（通過返回-1）。 識別出目標紙牌不在牌堆中最簡單的方法是，牌堆中沒有紙牌，也就是high小于low的情況。當然，牌堆中仍然有牌，我的意思是由low和high指定的段中沒有紙牌。 添加了high ~~~ int findBisect (const Card& card, const apvector<Card>& deck, int low, int high) { cout << low << ", " << high << endl; if (high < low) return -1; int mid = (high + low) / 2; if (equals (deck[mid], card)) return mid; if (deck[mid].isGreater (card)) { return findBisect (card, deck, low, mid-1); } else { return findBisect (card, deck, mid+1, high); } } ~~~ 我在開頭添加了一行輸出語句，這樣我們能查看遞歸調用序列并說服我們遞歸會走到基本條件。嘗試下面代碼 ~~~ cout << findBisect (deck, deck[23], 0, 51)); ~~~ 其輸出如下： ~~~ 0, 51 0, 24 13, 24 19, 24 22, 24 I found the card at index = 23 ~~~ 然后，我編造了1張不在牌堆中的牌——方塊15，然后試一下查找它，輸出如下： ~~~ 0, 51 0, 24 13, 24 13, 17 13, 14 13, 12 I found the card at index = -1 ~~~ 這些測試并不能證明程序的正確性，其實再多的數據也無法證明程序是正確的。但是看幾個例子并檢驗代碼，也許可以說服你自己。 遞歸調用的次數相當少，通常是6或7次。也就是說equals函數和isGreater函數只需要調用6或7次，而線性查找最多要調用52次。一般而言，二分查找比線性查找快的多，尤其是向量中元素數目很多時，效果更為明顯。 遞歸程序中兩個常見錯誤，一個是忘記了包含基本條件，另一個是遞歸調用永遠取不到基本條件。每個錯誤都會導致無窮遞歸，這種情況下C++最終會出現運行時錯誤。