插值查找

思路分析

原理介绍：

  1. 插值查找类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。
  2. 将折半查找中的求mid的公式进行了改进如下：

$$
mid = \frac{low+high}{2}=low+\frac{1}{2}(high-low) \quad => \quad mid=low+\frac{key-a[low]}{a[high]-a[low]}(high-low)
$$

  • 说明：low相当于left，high相当于right，key就是要找的值targetVal
  1. 插值查找求mid代码为：int midIndex = low + (high - low)*(key - a[low])/(a[high] - a[low])
  2. 相当于之前的$\frac{1}{2}$变成了与要查找的值有关的系数。改进了二分查找的：int mid = left + (right - left)

图解：

image-20241102171312731

最精髓的地方在于自适应的mid

注意事项：

  1. 对于数据量较大，关键字分布较均匀的查找表来说，采用插值查找，速度较快。
  2. 关键字分布不均的情况下，该方法不一定比二分查找要好。

代码实现

InsertValueSearch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package com.yukinoshita.algorithm.search;

public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i + 1;
        }

        int target = 100;
        int index = insertValueSearch(arr,0,arr.length-1,target);
        System.out.println("查找的目标值"+target+"的下标为："+index);

    }

    public static int insertValueSearch(int[] arr, int left, int right, int target) {
        int res = -1;
        //说明：target < arr[0] || target > arr[arr.length - 1]必须需要！
        //否则得到的mid值可能越界！(会导致某条语句出错……)
        if (left > right || target < arr[0] || target > arr[arr.length - 1]) {
            return res;
        }
        //求mid的公式
        int mid = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left]);
        int midVal = arr[mid];
        if (target > midVal) {
            res = insertValueSearch(arr, mid + 1, right, target);
        } else if (target < midVal) {
            res = insertValueSearch(arr, left, mid - 1, target);
        } else {
            res = mid;
        }
        return res;
    }

}