回顧 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; }
類似地,在 vsearch() 中, 最差的情況下,將需要 mn 次比對,才能找到或確定找不到。 當 u[] 和 v[] 沒有特殊結構,這樣子的結果無可避免。 但是,如果 u[] 和 v[] 都是排序好的數列, 就可以大量降低比對的次數。 這就留做習題了。
習題
注意:此處所有文件均為原著,個別的版權宣告日後會一一公布, 整體版面設計亦尚未完成。但仍請勿抄襲文字與圖片,以免觸犯著作權法。
Created: May 21, 2000
Last Revised: May 21, 2000
© Copyright 2000 Wei-Chang Shann 單維彰