1.原理介绍（基本与二分查找一样，查找中间值的公式变了）

（1）插值查询算法类似于二分查找，不同的是插值查找每次自适应mid处开始查找
（2）将折半查询查找中的求mid索引的公式，low表示左边索引left，high表示右边索引right。可以就是我们前面说的 findVal
image.png
（3）int mid = low +(high-low) (key -arr[low]) / (arr[high]-arr[low])
对应前面的代码公式:
int mid= left +(right-left) (key - arr[left]) / (arr[right] - arr[left])
（4）举例说明插值查找算法 1-100的数组
image.png

2.应用案例

请对一个有序数组进行插值查找{1,8, 10, 89, 1000,1234}，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示”没有这个数”。

代码实现

  1. public class InsertValueSearch {
  3.     public static void main(String[] args) {
  5. //        int [] arr = new int[100];
  6. //        for(int i = 0; i < 100; i++) {
  7. //            arr[i] = i + 1;
  8. //        }
  10.         int arr[] = { 1, 8, 10, 89,1000, 1234 };
  12.         int index = insertValueSearch(arr, 0, arr.length - 1, 1234);
  13.         //int index = binarySearch(arr, 0, arr.length, 1);
  14.         System.out.println("index = " + index);
  16.         //System.out.println(Arrays.toString(arr));
  17.     }
  18.         /*
  19.         二分查找代码
  20.         */
  21.     public static int binarySearch(int[] arr, int left, int right, int findVal) {
  22.         System.out.println("二分查找被调用~");
  23.         // 当 left > right 时，说明递归整个数组，但是没有找到
  24.         if (left > right) {
  25.             return -1;
  26.         }
  27.         int mid = (left + right) / 2;
  28.         int midVal = arr[mid];
  30.         if (findVal > midVal) { // 向 右递归
  31.             return binarySearch(arr, mid + 1, right, findVal);
  32.         } else if (findVal < midVal) { // 向左递归
  33.             return binarySearch(arr, left, mid - 1, findVal);
  34.         } else {
  36.             return mid;
  37.         }
  39.     }
  41.     //编写插值查找算法
  42.     //说明：插值查找算法，也要求数组是有序的
  43.     /**
  44.      *
  45.      * @param arr 数组
  46.      * @param left 左边索引
  47.      * @param right 右边索引
  48.      * @param findVal 查找值
  49.      * @return 如果找到，就返回对应的下标，如果没有找到，返回-1
  50.      */
  51.     public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
  54.         //注意：findVal < arr[0]  和  findVal > arr[arr.length - 1] 必须需要
  55.         //否则我们得到的 mid 可能越界（与二分查找的区别）
  56.         if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
  57.             return -1;
  58.         }
  60.         // 求出mid, 自适应
  61.         int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
  62.         int midVal = arr[mid];
  63.         if (findVal > midVal) { // 说明应该向右边递归
  64.             return insertValueSearch(arr, mid + 1, right, findVal);
  65.         } else if (findVal < midVal) { // 说明向左递归查找
  66.             return insertValueSearch(arr, left, mid - 1, findVal);
  67.         } else {
  68.             return mid;
  69.         }
  71.     }
  72. }

执行结果

  1. index = 4

3.插值查找注意事项

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