插值查找的簡單理解

• 2022 年 7 月 5 日
• 筆記
• 數據結構與算法, 查找, 算法

詳細描述

二分查找是通過折半的方法，每一次都將搜索範圍縮小至原來的二分之一，如果這個折半能夠實現到折四分之一甚至更多，效率將會更高。

插值查找就是這樣的算法，類似於二分查找，插值查找每次會從自適應處開始查找，實質上是將 \(\frac1 2\) 處位置的查找公式做了修改：

插值查找詳細的執行步驟如下：

1. 在有序表中，通過比例公式取對應記錄作為比較對象；
2. 若給定值與對應記錄的關鍵字相等，則查找成功；
3. 若給定值小於對應記錄的關鍵字，則在對應記錄的左半區繼續查找；
4. 若給定值大於對應記錄的關鍵字，則在中間記錄的右半區繼續查找；
5. 不斷重複上述過程，直到查找成功，或所有查找區域無記錄，查找失敗為止。

問題解疑

插值查找為什麼是 \(\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);
    }
}