C++ 二分查找

如果牌堆中的紙牌不是按順序排列的，那就沒有比線性查找更快的查找方法了。我們必須查看每張紙牌，因?yàn)槌酥馕覀儫o法確定要找的紙牌是不是在其中。

但是查詞典時(shí)，我們并不是從頭到尾、一個(gè)詞一個(gè)詞的查。因?yàn)閱卧~是以字母順序排列的，所以我們可以使用類似于二分查找的算法：

1. 從中間某個(gè)位置開始。
2. 在這一頁上選擇一個(gè)單詞，并用這個(gè)單詞和我們要查找的單詞比較。
3. 如果這就是我們要找的單詞，結(jié)束。
4. 如果我們要找的單詞在這一頁上的單詞之后，翻到后面某頁并回到第2步。
5. 如果我們要找的單詞在這一頁上的單詞之前，翻到詞典前面某頁并回到第2步。

如果遇到了這種情況，某頁上有兩個(gè)相鄰的單詞，而要找的單詞應(yīng)該在它們之間，這時(shí)即可確定詞典中沒要我們要查的單詞。唯一的例外就是單詞印錯地方了，但這就與單詞按字母順序排列的假設(shè)沖突了。

在牌堆這個(gè)例子中，如果知道紙牌是有序擺放的，我們就能寫一個(gè)更快的find函數(shù)。編寫二分查找最好的方法是利用遞歸函數(shù)，因?yàn)槎肿匀欢皇沁f歸的。

竅門是編寫findBisect函數(shù)，它以兩個(gè)索引值low和high為參數(shù)，用以確定要查找的向量的一段（包括low和high指定的元素）。

1. 要在向量中查找，選擇low和high之間的一個(gè)索引，我們稱之為mid。將mid指定的紙牌與我們要查找的牌相比。
2. 如果找到，結(jié)束。
3. 如果mid處的紙牌比要找的牌大，繼續(xù)在low和mid-1確定的區(qū)間中查找。
4. 如果mid處的紙牌比要找的牌小，繼續(xù)在mid+1和high確定的區(qū)間中查找。

可以懷疑第3步和第4步看起來像遞歸調(diào)用。我們將其轉(zhuǎn)化為C++代碼，看起來是這個(gè)樣子的：

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);
  }
}

雖然這段代碼已經(jīng)包含了二分查找的核心，但還是缺點(diǎn)什么。按照當(dāng)前代碼，如果要找的紙牌不再牌堆中，它會一直遞歸下去。我們需要找到一種方法來檢查這一條件并做出適當(dāng)?shù)奶幚恚ㄍㄟ^返回-1）。

識別出目標(biāo)紙牌不在牌堆中最簡單的方法是，牌堆中沒有紙牌，也就是high小于low的情況。當(dāng)然，牌堆中仍然有牌，我的意思是由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);
  }
}

我在開頭添加了一行輸出語句，這樣我們能查看遞歸調(diào)用序列并說服我們遞歸會走到基本條件。嘗試下面代碼

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

這些測試并不能證明程序的正確性，其實(shí)再多的數(shù)據(jù)也無法證明程序是正確的。但是看幾個(gè)例子并檢驗(yàn)代碼，也許可以說服你自己。

遞歸調(diào)用的次數(shù)相當(dāng)少，通常是6或7次。也就是說equals函數(shù)和isGreater函數(shù)只需要調(diào)用6或7次，而線性查找最多要調(diào)用52次。一般而言，二分查找比線性查找快的多，尤其是向量中元素?cái)?shù)目很多時(shí)，效果更為明顯。

遞歸程序中兩個(gè)常見錯誤，一個(gè)是忘記了包含基本條件，另一個(gè)是遞歸調(diào)用永遠(yuǎn)取不到基本條件。每個(gè)錯誤都會導(dǎo)致無窮遞歸，這種情況下C++最終會出現(xiàn)運(yùn)行時(shí)錯誤。