什麼是插補搜尋法？

Question

請問什麼是插補搜尋法？它的原理為何？請詳細說明zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

請附上參考資料來源

Answer 1

Algorithm Gossip: 插補搜尋法
說明
如果卻搜尋的資料分佈平均的話，可以使用插補（Interpolation）搜尋法來進行搜尋，在搜尋的對象大於500時，插補搜尋法會比 二分搜尋法 來的快速。

解法
插補搜尋法是以資料分佈的近似直線來作比例運算，以求出中間的索引並進行資料比對，如果取出的值小於要尋找的值，則提高下界，如果取出的值大於要尋找的值，則降低下界，如此不斷的減少搜尋的範圍，所以其本原則與二分搜尋法是相同的，至於中間值的尋找是透過比例運算。

int interpolation(int data[], int low, int high, int target) {
int mid = low + (target - data[low]) * (high - low) / (data[high] - data[low]);
return mid;
}
int interpolation_search(int data[], int n, int target) {
return do_search(data, 0, n-1, target);
}
int do_search(int data[], int low, int high, int target) {
int mid;
if (low > high) return (-1);
if (low == high) {
if (target == data[low]) return low;
else return (-1);
}
if ((target < data[low]) || (target > data[high])) return (-1);
mid = interpolation(data, low, high, target);
if (target == data[mid]) return mid;
if (target < data[mid]) return do_search(data, low, mid-1, target);
else return do_search(data, mid+1, high, target);
}
此法的時間複雜度取決於資料分佈的情況而定，平均而言優於O(log N)。
使用內插搜尋法資料需先經過排序。