java实现数据查找算法：插值查找

今天爱分享给大家带来java实现数据查找算法：插值查找，希望大家能够喜欢。

1，插值查找基本介绍
插值查找的前提条件是目标数组为有序数组
插值查找类似于二分查找，不同的是插值查找每次从自适应middle索引开始查找
插值查找其实就是对二分查找middle索引求值的优化，求值公式为：

int middle = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left])

二分查找到插值查找的公式演进如下：

举例说明：如果存在一个长度为20， 值为1-20的顺序一维数组，需要查找到1所在的索引。二分查找基本需要查找4次才能查找到；而通过插值查找索引在0位置的数据，只需要一次，即：

middle = 0 + (19 - 0) * (1 - 1) / (20 - 1) = 0;
arr[0] = 1;

2，插值查找代码实现

package com.self.datastructure.search;


/**
 * 进入查找
 *
 * @author PJ_ZHANG
 * @create 2020-03-13 15:37
 **/
public class InsertValueSearch {

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(insertValueSearch(array, 0, array.length - 1, 10));
    }

    /**
     * 进入查找获取到对应值索引
     * @param array 目标数组
     * @param left 左索引
     * @param right 右索引
     * @param target 目标值
     * @return
     */
    public static int insertValueSearch(int[] array, int left, int right, int target) {
        if (left > right) {
            return -1;
        }
        // 进入查找, 获取到自适应middle索引
        int middle = left + (right - left) * (target - array[left]) / (array[right] - array[left]);
        System.out.println("middle: " + middle);
        // 大于 向右查找
        if (target > array[middle]) {
            return insertValueSearch(array, middle + 1, right, target);
        } else if (target < array[middle]) { // 小于, 向左查找
            return insertValueSearch(array, left, middle - 1, target);
        } else {
            return middle;
        }
    }

}

3，注意事项
对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快
关键字不均匀的情况下，该方法不一定比二分查找速度快