(二十一）查找算法-插值查找

1 基本介绍

1.1 插值查找

插值查找算法又称插值搜索算法，是在二分查找算法的基础上改进得到的一种查找算法。

插值查找算法只适用于有序序列，换句话说，它只能在升序序列或者降序序列中查找目标元素。作为“改进版”的二分查找算法，当有序序列中的元素呈现均匀分布时，插值查找算法的查找效率要优于二分查找算法；反之，如果有序序列不满足均匀分布的特征，插值查找算法的查找效率不如二分查找算法。

所谓均匀分布，是指序列中各个相邻元素的差值近似相等。例如，{10, 20, 30, 40, 50} 就是一个均匀分布的升序序列，各个相邻元素的差值为 10。再比如 {100, 500, 2000, 5000} 是一个升序序列，但各相邻元素之间的差值相差巨大，不具备均匀分布的特征。

插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。

将折半查找中的求 mid 索引的公式，low 表示左边索引，high 表示右边索引。

注意：key代表需要查找的值。

插值查找的mid 值是通过公式计算得来由，由公式可以明显看出mid的值并非像二分那样为左右索引的中间位置。

int midIndex = low + (high-low)*(key-arr[low])/(arr[high]-arr[ow])；/*插值索引*/

插值查找的特点：
（1）查找的序列必须有序

（2）对于数据量大的以及关键字分布均匀的有序序列来说，插值查找的速度较快。

（3）对于分布不均匀的有序序列来说，该算法不一定比二分查找要好。

插值查找算法的解题思路：
对于已经学过二分查找算法的读者来说，学习插值查找算法会变得非常容易，因为插值查找算法完全照搬了二分查找算法的解题思路，仅对一些实现细节做了修改。

首先，我们通过一个实例回忆一下二分查找算法的解题思路。例如，在 {1,2,3,4,5,6,7,8,9,10} 升序序列中查找元素 2，二分查找算法的查找过程如下图所示：

如上图所示，先找到搜索区域中的中间元素，然后和目标元素进行比较，如果相同表示查找成功；反之，根据比较结果选择中间元素左侧或右侧的区域作为新的搜索区域，以同样的方式继续查找。

插值查找算法的解题思路和二分查找算法几乎相同，唯一的区别在于，每次与目标元素做比较的元素并非搜索区域内的中间元素，此元素的位置需要通过如下公式计算得出：

int midIndex = low + (high-low)*(key-arr[low])/(arr[high]-arr[low])；/*插值索引*/

式子中，各部分的含义分别是：

midIndex：计算得出的元素的位置；

high：搜索区域内最后一个元素所在的位置；

low：搜索区域内第一个元素所在的位置；

key：要查找的目标元素；

arr[]：表示整个待搜索序列。

为了方便讲解，我们仍将 Mid 位置上的元素称为 “中间元素”。

使用插值查找算法在 {1,2,3,4,5,6,7,8,9,10} 升序序列中查找元素 2，查找过程如下：

假设序列中各个元素的位置为 0~9，搜索区域为整个序列，通过公式计算出 “中间元素” 的位置：

midIndex = 0 + (9-0) *(2-1)/(10-1)

“中间元素” 的位置为 1，也就是元素 2，显然这是我们要找的目标元素，查找结束。整个查找过程如下所示：

对比两图不难看出，在 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 这个满足均匀分布的升序序列中查找元素 2，插值查找算法的执行效率要优于二分查找算法。

2 代码实现

/*** 插值查找*/
public class InsertValueSearch {public static void main(String[] args) {int[] arr = new int[100];for (int i = 0; i < arr.length; i++) {arr[i] = i;}System.out.println(Arrays.toString(arr));int index = insertValueSearch(arr, 0, arr.length - 1, 68);System.out.println("index = " + index);}/*** 插值查找** @param arr     数组* @param left    左边索引* @param right   右边索引* @param findVal 查找的值* @return*/public static int insertValueSearch(int[] arr, int left, int right, int findVal) {if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {return -1;}// 求出midint mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);int midVal = arr[mid];if (findVal > midVal) {return insertValueSearch(arr, mid + 1, right, findVal);} else if (findVal < midVal) {return insertValueSearch(arr, left, mid - 1, findVal);} else {return mid;}}
}