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

標籤

2010年12月1日 星期三

[ 資料結構 小學堂 ] 搜尋 : 內插搜尋法 (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. 使用內插搜尋法, 資料必須先經過排序.

範例代碼 : 

  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, 50049);  // 內插搜尋法的資料必須排序過. 這裡使用快速排序法  
  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#####

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!