常见的查找算法（三）：插值查找

插值搜索法（Interpolation search）是利用插值公式来计算猜测搜索键值的位置。搜索方式与二分搜索相同

插值公式：

插值 = (设算数 - 最小数) / (最大数 - 最小数)

搜索键值 = left + parseInt( ( key - data[ left ] ) / ( data[ right ] - data[ left ] ) ) * ( right - left ) )

插值搜索之算法与二分搜索算法几乎完全相同，差别在：

二分搜索法：猜测键值在中间位置(middle)
插值搜索法：用插值公式计算键值位置

插值算法代码如下：

 1     /**
 2      * 差值查找的最好的一个典型就是翻词典，当你要翻一个c开头的词，你不会打开书中间往两边查找，
 3      * 而是往靠前的那个位置去翻，插值查找就是对查找的范围查找的元素按比例做出调整。
 4      * 这种算法比较适合较大的数组，还有数组中分布的值大小要比较均匀。
 5      * <p>总结：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。
 6      * 反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。</p>
 7      * 本例子使用不均匀且量小的例子。所以比较的次数比较多。
 8      */
 9     public static int insertSearch(int[] a, int value, int low, int high) {
10         int mid = low + ((value - a[low]) / (a[high] - a[low])) * (high - low);
11         count++;
12         if (a[mid] == value)
13             return mid;
14         count++;
15         if (a[mid] > value)
16             return insertSearch(a, value, low, mid - 1);
17         else
18             return insertSearch(a, value, mid + 1, high);
19     }

　　这种算法比较适合较大的数组，还有数组中分布的值大小要比较均匀。

　　最坏时间复杂度O(n)，最好时间复杂度O(1)，平均时间复杂度O(log₂(log₂n))。

　　测试代码：

 1     public static void main(String[] args) {
 2         int[] arr = {1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22};
 3 
 4         //二分查找的前提是在排好序的数组中查找
 5         QuickSort.quickSorts(arr, 0, arr.length - 1);
 6         System.out.println(Arrays.toString(arr));
 7 
 8         int result = insertSearch(arr, 4, 0, arr.length - 1);
 9 
10         if (result != -1)
11             System.out.println("在数组中的位置：" + (result + 1));
12         else
13             System.out.println("要查找的数不出存在");
14 
15         System.out.println("比较次数："+count);
16     }