C++ 二分查找

2023-03-20 16:24 更新

如果牌堆中的紙牌不是按順序排列的,那就沒有比線性查找更快的查找方法了。我們必須查看每張紙牌,因為除此之外我們無法確定要找的紙牌是不是在其中。

但是查詞典時,我們并不是從頭到尾、一個詞一個詞的查。因為單詞是以字母順序排列的,所以我們可以使用類似于二分查找的算法:

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

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

在牌堆這個例子中,如果知道紙牌是有序擺放的,我們就能寫一個更快的find函數(shù)。編寫二分查找最好的方法是利用遞歸函數(shù),因為二分自然而然是遞歸的。

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

  1. 要在向量中查找,選擇low和high之間的一個索引,我們稱之為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++代碼,看起來是這個樣子的:

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)包含了二分查找的核心,但還是缺點什么。按照當前代碼,如果要找的紙牌不再牌堆中,它會一直遞歸下去。我們需要找到一種方法來檢查這一條件并做出適當?shù)奶幚恚ㄍㄟ^返回-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);
  }
}

我在開頭添加了一行輸出語句,這樣我們能查看遞歸調(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ù)據(jù)也無法證明程序是正確的。但是看幾個例子并檢驗代碼,也許可以說服你自己。

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

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

以上內(nèi)容是否對您有幫助:
在線筆記
App下載
App下載

掃描二維碼

下載編程獅App

公眾號
微信公眾號

編程獅公眾號