詳細描述
二分查找是通過折半的方法，每一次都將搜索范圍縮小至原來的二分之一，如果這個折半能夠實作到折四分之一甚至更多，效率將會更高，
插值查找就是這樣的演算法，類似于二分查找，插值查找每次會從自適應處開始查找，實質上是將 \(\frac1 2\) 處位置的查找公式做了修改：
\[mid = \frac{low + high}{2} = low + \frac{1}{2}(high - low) \Rightarrow mid = low + \frac{key - a[low]}{a[high] - a[low]}(high - low) \]插值查找詳細的執行步驟如下：
- 在有序表中，通過比例公式取對應記錄作為比較物件；
- 若給定值與對應記錄的關鍵字相等，則查找成功；
- 若給定值小于對應記錄的關鍵字，則在對應記錄的左半區繼續查找；
- 若給定值大于對應記錄的關鍵字，則在中間記錄的右半區繼續查找；
- 不斷重復上述程序，直到查找成功，或所有查找區域無記錄，查找失敗為止，
問題解疑
插值查找為什么是 \(\frac{key - a[low]}{a[high] - a[low]}\)?
打個比方，在一本英文字典中查找 apple 這個單詞的時候，肯定不會從字典中間開始查找，而是從字典開頭部分開始翻，因為會覺得這樣的找法才是比較快的，
對于一個有序的序列，如果能在查找前較準確的預測關鍵字在序列中的位置時，這樣的查找方法能比二分查找擁有更好的性能，
其中的差值公式 \(\frac{key - a[low]}{a[high] - a[low]}\) 是要將查找的關鍵字與序列中的最大、最小記錄的關鍵字比較，獲取一個相對更準確的位置，
使用插值查找有哪些注意事項？
對于均勻分布的序列，插值查找的效率是非常快，特別是對于絕對均勻分布的序列（相鄰元素差值相同），插值查找可以只做一次比較就查找成功，
對于分布很不均勻的序列，插值查找的計算則會起到反效果，這時候反而不如二分查找，
代碼實作
查找介面
package cn.fatedeity.algorithm.search;
public interface Search {
int search(int[] numbers, int target);
}
插值查找類
package cn.fatedeity.algorithm.search;
/**
* 插值查找類
*/
public class InterpolationSearch implements Search {
private int search(int[] numbers, int target, int left, int right) {
if (left > right) {
return -1;
} else if (left == right) {
if (numbers[left] == target) {
return left;
} else {
return -1;
}
}
if (target < numbers[left] || target > numbers[right]) {
return -1;
}
int scale = (target - numbers[left]) / (numbers[right] - numbers[left]);
int mid = left + (int) Math.floor(scale * (right - left));
if (numbers[mid] > target) {
return this.search(numbers, target, left, mid - 1);
} else if (numbers[mid] < target) {
return this.search(numbers, target, mid + 1, right);
} else {
return mid;
}
}
@Override
public int search(int[] numbers, int target) {
return this.search(numbers, target, 0, numbers.length - 1);
}
}
首發于翔仔的個人博客，點擊查看更多，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498625.html
標籤：其他