public class InsertValueSearch {public static void main(String[] args) {int[] a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};System.out.println(insertValueSearch(a, 0, a.length - 1, 4));}/*** 插值查找* 查找的数组必须是有序！* 适用于：数据量大，关键字分布比较均匀；关键字分布不均匀，该方法不一定比折半查找好。** @param arr* @param left* @param right* @param findVal 要查找的值* @return 找到：返回下标；没有找到：返回-1*/public static int insertValueSearch(int[] arr, int left, int right, int findVal) {System.out.println("查找次数~");//数据校验if (left > right || findVal < arr[left] || findVal > arr[right]) {return -1;}//重点！！！！！int mid = left + (right - left) * (findVal - arr[left]) / arr[right] - arr[left];int midVal = arr[mid];if (findVal < midVal) {//向左查找return insertValueSearch(arr, left, mid - 1, findVal);} else if (findVal > midVal) {return insertValueSearch(arr, mid + 1, right, findVal);} else {return mid;}}
}