快速搜尋

回顧 search(),考慮最差狀況, 這個函式需要執行幾次比對動作呢? 最差就是找不到的時候,需要比對 n 次。也就是說, 必需把 v[] 中的每個元素都與 x 比對一遍, 才能決定找不到。

在我們事先不知道任何 v[] 的任何性質之情況下, 這似乎沒有改良的空間。 但是,如果我們知道 v[] 是非漸減數列, 也就是 v[i] <= v[i+1],那就不同了。 這裡介紹一種二分搜尋法,在最差狀況,也只不過需要大約 log2 n 次的比對步驟。 若 n 是 1000,則 n 和 log2 n 大約是 1000 和 10 的差別, 可謂是巨大的改良。 於是,我們就知道,排序的重要性了。

此處用一個例子,簡介二分搜尋的概念。 例如 v[] 有 12 個元素,依序是

2 3 5 7 9 11 13 17 19 23 29 31
現在,若要找 19,則先取 v[] 的中央數,亦即 v[5], 但 v[5] 是 11,比 19 小。 由於 v[1]---v[4] 都不大於 v[5], 所以它們都不可能是 19。剩下的候選人只剩下 v[] 中的一半元素: v[6]---v[11]。 接著,再取 v[6]---v[11] 這個子數列來做二分搜尋。 這次的中央數是 v[8],恰好就是 19,於是就找到了。 底下,以搜尋的圖示,來表現試圖搜尋 18 的結果 (找不到)。
2 3 5 7 9 11 13 17 19 23 29 31
          18
             13 17 19 23 29 31
                   18
             13 17
             18
                17
                18


int binsearch(int v[], unsigned int n, int x) {
    int a, b, m;
    a = 0;
    b = n-1;
    while (a <= b) {
        m = (a+b)/2;
        if (v[m] > x)
            b = m-1;
        else if (v[m] < x)
            a = m+1;
	else
            return m;
    }
    retuen -1;
}

binsearch() 中的 a 和 b 就分別是需要搜尋的子數列之左端點和右端點。

類似地,在 vsearch() 中, 最差的情況下,將需要 mn 次比對,才能找到或確定找不到。 當 u[]v[] 沒有特殊結構,這樣子的結果無可避免。 但是,如果 u[]v[] 都是排序好的數列, 就可以大量降低比對的次數。 這就留做習題了。

習題

  1. 如果 u[]v[] 分別是已經排序好的 int 序列 (漸增排序)。寫一個函式 qsearch(),盡可能地快速比對兩個序列。 如果沒有相同的元素,返回 -1,否則返回使得 u[i] == v[j] 的最小足標 i。 如果 u[]v[] 的維度分別是 m 和 n, 說明您的程式,在最差狀況下,需要比對幾次? (說明寫在原始碼的註解裡面。)
  2. 用遞迴方法設計一個應用二分搜尋法的函式。

[ 前一節 ]‧[ 後一節 ]‧[ 回目錄 ]



注意:此處所有文件均為原著,個別的版權宣告日後會一一公布, 整體版面設計亦尚未完成。但仍請勿抄襲文字與圖片,以免觸犯著作權法。

Created: May 21, 2000
Last Revised: May 21, 2000
© Copyright 2000 Wei-Chang Shann 單維彰

shann@math.ncu.edu.tw