[ 資料結構 小學堂 ] 搜尋 : 內插搜尋法 (Interpolation Search)

前言 : 
內插搜尋法又叫插補搜尋法, 是二分搜尋法的改良版. 它是依照資料位置的分佈, 利用公式預測資料的所在位置, 再以二分法的方式漸漸逼近. 使用內插法是假設資料平均分布在陣列中, 而每一筆資料的差距是相當接近或是有一定的距離比例. 其內插法的公式為 : 
Mid = low + ((key-data[low])) / (data[high] - data[low])) * (high - low) 

其中 key 是要找尋的鍵, data[high], data[low] 是剩餘待找尋紀錄中的最大值與最小值, 對資料筆數 n , 其插補搜尋法的步驟如下 : 

1. 將紀錄由小到大的順序予與 1,2,3..n 的編號.
2. 令 low=1, high=n.
3. 當low < high 時, 重複步驟1及步驟5.
4. 令 Mid = low + ((key-data[low])) / (data[high] - data[low])) * (high - low).
5. 若 Key < Key(Mid) 且 low != Mid-1, 則令 high = Mid-1.
6. 若 key = key(Mid) 表示成功搜尋到鍵值位置.
7. 若 Key > Key(Mid) 且 high != Mid+1, 則令 low = Mid+1.

內插法分析 : 

1. 一般而言, 內插搜尋法優於循序搜尋法, 而且如果資料的分布愈平均, 則搜尋速度愈快, 甚至可能第一次就照到資料. 此法的時間複雜度取決於資料分布的情況而定, 平均優於 O(logn).
2. 使用內插搜尋法, 資料必須先經過排序.

範例代碼 : 

view plaincopy to clipboardprint?

1. #include   
2. #include   
3. #include   
4. #include   
5.   
6. using namespace std;  
7. struct BenchMark {  
8.     int swapTime;  // Swap Time  
9.     int verifyTime;  // Verify Time  
10.     double cTime;  // Consumed Time  
11. };  
12. void _swapValue(int *a, int *b) {  
13.     int tmp = *a;  
14.     *a = *b;  
15.     *b = tmp;  
16. }  
17. void quickSort(int data[], int n, int i, int j) {  
18.     if(i >= j)  
19.         return;  
20.     int m=0, left=i+1, right=j;  
21.     int cnt=0, vt=0;  
22.     while(left
23.         vt++;  
24.         if(data[left]<=data[i]) {  
25.             left++;           
26.             continue;  
27.         }  
28.         vt++;  
29.         if(data[right]>=data[i]) {  
30.             right--;              
31.             continue;  
32.         }         
33.         _swapValue(&data[left], &data[right]);  
34.         cnt++;  
35.         left++;  
36.         right--;  
37.     }  
38.     if(data[i]
39.         right--;  
40.     }  
41.     _swapValue(&data[i], &data[right]);   
42.     quickSort(data, n, i, right-1);   
43.     quickSort(data, n, right+1, j);  
44. }  
45. int interSearch(int data[50], int val) {      
46.     int low=0, mid, high=49;  
47.     int tmpLow, tmpHigh;  
48.     cout << "搜尋處理中(使用內插搜尋法)..." << endl;  
49.     if(val <= data[high] && val >= data[low]) {                 
50.         while(low<=high && val !=-1) {             
51.             tmpLow = low; tmpHigh = high;  
52.             if(val == data[high]) return high;  
53.             if(val == data[low]) return low;  
54.             if(data[low]>val || data[high]break;  
55.             printf("Current low=%d, high=%d...\t", low, high);  
56.             mid = low + ((val - data[low]) * (high - low) / (data[high] - data[low]));  
57.             printf("Using mid=%d\n", mid);  
58.             if (data[mid] > val) {  
59.                 high = mid - 1;  
60.             } else if(data[mid] < val) {  
61.                 low = mid + 1;  
62.             } else if(data[mid] == val) {                 
63.                 return mid;  
64.             }  
65.             if(tmpLow == low && tmpHigh == high) {  
66.                 printf("low=%d with data[low]=%d\n", low, data[low]);  
67.                 printf("high=%d with data[high]=%d\n", high, data[high]);  
68.                 printf("mid=%d with data[mid]=%d\n", mid, data[mid]);  
69.                 system("pause");  
70.             }  
71.         }  
72.     }  
73.      
74.     return -1;  
75. }  
76. void main() {  
77.     int data[50] = {0}, val=1;  
78.     for(int i=0; i<50; i++) {  
79.         data[i] = val;  
80.         val+=(rand()%5+1);  
81.     }  
82.     quickSort(data, 50, 0, 49);  // 內插搜尋法的資料必須排序過. 這裡使用快速排序法  
83.     int key=0, num;  
84.     while(1) {  
85.         cout << "請輸入搜尋值(1-150), 輸入-1結束: ";  
86.         cin >> key;  
87.         if(key<0)  
88.             break;  
89.         num = interSearch(data, key);  
90.         if(num>=0) {  
91.             cout << "在第 " << num << "個位置找到 ( data[" << num << "]=" << data[num] << "." << endl;   
92.         } else {  
93.             cout << "##### 沒有找到 " << key << "#####" << endl;  
94.         }  
95.     }  
96. }  

執行結果 : 

請輸入搜尋值(1-150), 輸入-1結束: 68 <輸入查詢數值>
搜尋處理中(使用內插搜尋法)...
Current low=0, high=49... Using mid=22
在第 23個位置找到 ( data[23]=68.
請輸入搜尋值(1-150), 輸入-1結束: 69
搜尋處理中(使用內插搜尋法)...
Current low=0, high=49... Using mid=22
Current low=23, high=49... Using mid=23
##### 沒有找到 69#####