插值查找算法

先来看一个场景

/**
     * 先来看一个场景，在二分查找中查找需要几次
     */
    @Test
    public void binary2Test() {
             int[] arr = new int[]{1, 8, 10, 89, 1000, 1000, 1234, 1234};
        int findVal = 1;
        Integer result = binary(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == null ? "未找到" : "找到值，索引为：" + result));

        findVal = 1000;
        result = binary(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = 1234;
        result = binary(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = 12345;
        result = binary(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = 89;
        result = binary(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));
    }

    /**
     * @param arr
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 要查找的值
     * @return 未找到返回 -1，否则返回该值的索引
     */
    private int binary(int[] arr, int left, int right, int findVal) {
        System.out.println("binary");
        // 当找不到时，则返回 -1
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        // 相等则找到
        if (midVal == findVal) {
            return mid;
        }
        // 要查找的值在右边，则右递归
        if (findVal > midVal) {
            // mid 的值，就是当前对比的值，所以不需要判定
            return binary(arr, mid + 1, right, findVal);
        }
        return binary(arr, left, mid - 1, findVal);
    }

查找值 1 的输出测试

binary
binary
binary
查找值 1：找到值，索引为：0
binary
binary
查找值 1000：找到值，索引为：5
binary
binary
binary
查找值 1234：找到值，索引为：6
binary
binary
binary
binary
binary
查找值 12345：未找到
binary
查找值 89：找到值，索引为：3

上面是使用上次的二分查找法，查找一个数字 1，可以看到查找了 3 次，能否通过一种方式，来改进 mid ，快速定位呢?

查找原理

1. 查找查找算法 类似二分查找

   不同的是插值查找每次从 自适应 mid 处开始查找

2. 将折半查找中求 mid 的索引公式进行改进

   

   • low：表示左边索引
   • high：表示右边所以
   • key：表示要查找的值

   将折半查找中的 二分之一 这个系数进行改写，其他不变。

3. 改写后的查找索引求值为

   int mid = low + (high - low) * (key -arr[low]) / (arr[high] - arr[low]) 
   										// 这一块就是上面公式中的分数表达式
   

下面对一个数组 1~100 的有序数组进行查找讲解：

arr[] = [1,2,3,4...100]

查找数字 1
使用二分查找法：需要多次折半，才能找到
使用插值查找：
int mid = low + (high - low) * (key -arr[low]) / (arr[high] - arr[low]) 
int mid = 0 + （99 - 0） * （1 - 1） / (100 - 1) = 0 + 99 * 0 / 99 = 0
一次就定位了。

查找数字 100
int mid = 0 + （99 - 0） * （100 - 1） / (100 - 1) = 0 + 99 * 99 / 99 = 99

查找数字 50
int mid = 0 + （99 - 0） * （50 - 1） / (100 - 1) = 0 + 99 * 49 / 99 = 0 + 49 = 49

可以看到对于这种连续性的，基本上就是一次性就找到了。

代码实现

   @Test
    public void insertValueTest() {
        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i + 1;
        }

        int findVal = 1;
        int result = insertValueSearch(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = 50;
        result = insertValueSearch(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = 100;
        result = insertValueSearch(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));
    }

    public int insertValueSearch(int[] arr, int left, int right, int findValue) {
        System.out.println("insertValueSearch");
//        if (left > right) {
//            return -1;
//        }
        // 这里可以对未找到进行优化
        // 同时对于查找的边界判定来说是必须的，因为 mid 求职是根据值来求，不进行边界判定，有可能就越界了
        if (left > right || findValue < arr[0] || findValue > arr[arr.length - 1]) {
            return -1;
        }
        int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);
        if (arr[mid] == findValue) {
            return mid;
        }

        // 当查找值大于该值，则表示目标值在左侧
        if (findValue > arr[mid]) {
            return insertValueSearch(arr, left, mid - 1, findValue);
        }

        // 当查找值小于该值，则表示目标值在右侧
        return insertValueSearch(arr, mid + 1, right, findValue);
    }

可以看到上面的代码，除了求 mid 值与折半查找不一样外，其他的都一样

测试输出

insertValueSearch
查找值 1：找到值，索引为：0
insertValueSearch
查找值 50：找到值，索引为：49
insertValueSearch
查找值 100：找到值，索引为：99

和原理中推导的一直，都是一次就找到了

那么再测试下非连续数组

/**
     * 查找非连续性的值
     */
    @Test
    public void insertValueTest2() {
        int[] arr = new int[]{1, 8, 10, 89, 1000, 1000, 1234, 1234};

        int findVal = 1;
        int result = insertValueSearch(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = 1000;
        result = insertValueSearch(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = 1234;
        result = insertValueSearch(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = 12345;
        result = insertValueSearch(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = 89;
        result = insertValueSearch(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));
    }

测试输出

nsertValueSearch
查找值 1：找到值，索引为：0
insertValueSearch
查找值 1000：找到值，索引为：5
insertValueSearch
查找值 1234：找到值，索引为：7
insertValueSearch
查找值 12345：未找到
insertValueSearch
insertValueSearch
insertValueSearch
insertValueSearch
查找值 89：找到值，索引为：3

对比来看，大部分的值，只查找 1 次，就定位了，对于 89 来说，却比二分查找多了好几次。

所以：插值查找也有他的使用场景和注意事项

注意事项

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