[ 資料結構 小學堂 ] 搜尋 : 費氏搜尋法

前言 : 
費氏搜尋法 (Fibonacci Search) 又稱費伯那搜尋法, 此法與二分法一樣都是以切割範圍來進行搜尋, 不同的是費氏搜尋法不以對稱(對半)切割而是以費氏及數的方式切割. 費氏級數 F(n) 定義如下 : 

費氏級數 : 0,1,1,2,3,5,8,... . 也就是除了第0 及第1 個元素外, 每個值都是前兩個的值的加總. 費式搜尋法的好處是只用到加減運算而不需用到乘法及除法, 這種以電腦運算的過程來看效率會高於前兩種搜尋法 (二元搜尋法與循序搜尋法). 

費式搜尋樹 : 
在尚未介紹費式搜尋法之前, 我們先來認識費式搜尋樹. 所謂的費式搜尋樹是以費氏級數的特性所建立的二元樹, 其建立原則如下 : 

1. 費式樹的左右子樹均為費式樹.
2. 當資料個數 n 決定, 若想決定費氏樹的階層k 值為何, 我們必須找到一個最小的 k 值, 使得費式級數的 Fib(k+1) >= n+1.
3. 費氏樹的樹根定為一費氏樹, 且子節點與父節點的差值絕對為費氏樹.
4. 當 k>=2, 費氏樹的樹根為 Fib(k), 左子樹為 (k-1) 階費氏樹 (其樹根為 Fib(k-1)), 右子樹為 (k-2) 階費氏樹 (其樹根為 Fib(k) + Fib(k-2)).
5. 若 n+1 值不為費氏樹的值, 則可以找出一個 m 使用 Fib(k+1) - m = n+1, m = Fib(k+1)-(n+1), 再依費氏樹的建立原則完成費氏樹的建立, 最後費氏樹的各節點再減去差值 m 即可, 並把小於 1 的節點去掉即可.

也就是說當資料個數為 n, 且我們找到一個最小的費氏樹 Fib(k+1) 使得 Fib(k+1) > n+1. 則 Fib(k) 就是這棵費氏樹的樹根, 而 Fib(k-2) 則是與左右子樹開始的差值, 左子樹用減的 ; 右子樹用加的. 例如我們來實際求得 n = 33 的費氏樹 : 

1. 由於 n = 33, 且 n+1 = 34 為一費氏樹 (Fib(9)=34) , 故 Fib(k+1)=34 -> k=8, 建立二元樹的樹根為 Fib(8)=21.
2. 左子樹樹根為 Fib(8-1) = Fib(7) = 13
3. 右子樹樹根為 Fib(8) + Fib(8-2) = 21 + 8 = 29

依此原則我們可以建立如下的費氏樹 : 
 

費氏搜尋法 : 
費氏搜尋法是以費氏搜尋樹來找尋資料, 如果資料的個數為 n, 而且 n 比某一費氏樹小, 且滿足如下運算式 : 
Fib(k+1) >= n+1 

此時 Fib(k) 就是這棵費氏樹的樹根, 而 Fib(k-2) 則是與左右子樹開始的差值, 若我們要尋找的鍵值為 key, 首先比較陣列索引 Fib(k) 和鍵值 key, 此時可以有下列三種比較情況 : 

1. 當 key 值比較小, 表示所要找的鍵值 key 落在 1 到 Fib(k)-1 之間, 故繼續尋找 1 到 Fib(k)-1 之間的資料.
2. 如果鍵值與陣列索引 Fib(k) 的值相等, 表示成功搜尋到所要的資料.
3. 當 key 值比較大, 表示所要找的鍵值 key 落在 Fib(k) + 1 到 Fib(k+1) - 1 之間, 故繼續尋找 Fib(k)+1 到 Fib(k+1)-1 之間的資料.

費氏法分析 : 

1. 平均而言, 費氏搜尋法的比較次數會少於二元搜尋法, 但在最壞情況下則二元搜尋法較快. 其平均時間複雜度為 O(log2N).
2. 費式搜尋法較為複雜, 需要額外產生費氏樹.

範例代碼 : 

view plaincopy to clipboardprint?

1. #include   
2. using namespace std;  
3.   
4. #define FIB_SEARCH_MAX_LEN 20  
5. int _fib(int n) {  
6.     if(n == 0 || n==1)  
7.         return n;  
8.     return _fib(n-1) + _fib(n-2);  
9. }  
10.   
11. int fibSearch(int data[FIB_SEARCH_MAX_LEN], int key) {  
12.     cout << "搜尋處理中(使用費氏搜尋法)..." << endl;  
13.   
14.     int index = 2;  
15.     // 費氏數列的 k 值計算  
16.     while(_fib(index) <= FIB_SEARCH_MAX_LEN)  
17.         index++;  
18.     index--;  
19.     printf("Using key=%d...\n", index);  
20.     int rootNode = _fib(index);  
21.     int diff1 = _fib(index-1);  // 上一個費氏數  
22.     int diff2 = _fib(index-2);  // 上兩個費氏數  
23.     rootNode--;  // 配合陣列的索引是從 0 開始.  
24.     printf("Root Node=%d...\n", rootNode);  
25.     while(1) {  
26.         printf("\tData[%d]=%d...\n", rootNode, data[rootNode]);  
27.         if(key == data[rootNode]) {  
28.             return rootNode;  
29.         } else {  
30.             if(index==2) break;  // 沒有找到  
31.             if(key < data[rootNode]) {  
32.                 rootNode = rootNode - diff2; // 左子樹的新樹根  
33.                 printf("左子樹新樹根=%d...\n", rootNode);  
34.                 int temp = diff1;  
35.                 diff1 = diff2;              // 上一個費氏樹  
36.                 diff2 = temp - diff2; // 上兩個費氏樹  
37.                 index = index-1;  
38.             } else {  
39.                 if(index==3) break;  // 沒有找到  
40.                 rootNode = rootNode + diff2; // 右子樹的新樹根  
41.                 printf("右子樹新樹根=%d...\n", rootNode);  
42.                 diff1 = diff1 - diff2;  // 上一個費氏樹  
43.                 diff2 = diff2 - diff1;  // 上兩個費氏樹  
44.                 index = index -2;  
45.             }  
46.         }  
47.     }  
48.     return -1;  
49. }  
50. void main() {  
51.     int data[] = {5, 7, 12, 23, 25, 37, 48, 54, 68, 77, 91, 99, 102, 110, 118, 120, 130, 135, 136, 150};  
52.     printf("Source data:\n");  
53.     for(int i=0; i<4; i++) {  
54.         for(int j=0; j<5; j++)   
55.             printf("data[%2d] = %3d\t", i*5+j, data[i*5+j]);  
56.         printf("\n");  
57.     }  
58.     int key = 0, num;  
59.     while(1) {  
60.         cout << "請輸入搜尋值(1-150), 輸入-1結束: ";  
61.         cin >> key;  
62.         if(key<0)  
63.             break;  
64.         num = fibSearch(data, key);  
65.         if(num>=0) {  
66.             cout << "在第 " << num << "個位置找到 ( data[" << num << "]=" << data[num] << "." << endl;   
67.         } else {  
68.             cout << "##### 沒有找到 " << key << "#####" << endl;  
69.         }  
70.     }  
71. }  

執行結果 : 

Source data:
data[ 0] = 5 data[ 1] = 7 data[ 2] = 12 data[ 3] = 23 data[ 4] = 25
data[ 5] = 37 data[ 6] = 48 data[ 7] = 54 data[ 8] = 68 data[ 9] = 77
data[10] = 91 data[11] = 99 data[12] = 102 data[13] = 110 data[14] = 118
data[15] = 120 data[16] = 130 data[17] = 135 data[18] = 136 data[19] = 150
請輸入搜尋值(1-150), 輸入-1結束: 77 <輸入搜尋的鍵值>
搜尋處理中(使用費氏搜尋法)...
Using key=7...
Root Node=12...
Data[12]=102...
左子樹新樹根=7...
Data[7]=54...
右子樹新樹根=10...
Data[10]=91...
左子樹新樹根=9...
Data[9]=77...
在第 9個位置找到 ( data[9]=77.
請輸入搜尋值(1-150), 輸入-1結束: 103
搜尋處理中(使用費氏搜尋法)...
Using key=7...
Root Node=12...
Data[12]=102...
右子樹新樹根=17...
Data[17]=135...
左子樹新樹根=15...
Data[15]=120...
左子樹新樹根=14...
Data[14]=118...
左子樹新樹根=13...
Data[13]=110...
##### 沒有找到 103#####