插值查找，有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找，将查找点的选择改进为自适应选择，提高查找效率。
对于一个有序且分布均匀的数组，使用差值查找比使用二分查找要快很多
public static void main(String[] args) {int[] arr = new int[33];for (int i = 0; i < 33; i++) {arr[i] = i + 1;}System.out.println(insertValueSearch(arr,0,arr.length-1,23));}/*** 插值查找 需要数组是有序的* @param arr 目标数组* @param left 左边索引* @param right 右边索引* @param findValue 要查找的值* @return 如果找到，就返回对应的下标，如果没找到，就返回-1*/public static int insertValueSearch(int[] arr,int left,int right,int findValue){System.out.println("--");if (left > right || findValue < arr[left] || findValue > arr[right]) {return -1;}//求出midint mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);int midVal = arr[mid];if(findValue > midVal){//说明应该向右递归return insertValueSearch(arr,mid + 1,right,findValue);}else if(findValue < midVal){//说明应该向左递归return insertValueSearch(arr,left,mid-1,findValue);}else{return mid;}}