今天爱分享给大家带来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，注意事项
对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快
关键字不均匀的情况下，该方法不一定比二分查找速度快