插值查找（两种方法）

一、什么是插值查找

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

（2）二分查找中mid值是left和right所指序列下标的和的1/2即 mid = （left+right）/ 2。

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

（4）插值查找公式；3、int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;low表示左边索引left,high表示右边索引right. key 就是需要查找的值。

二、插值查找的特点

（1）查找的序列必须有序

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

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

三、代码实现

（1）方法一：递归

public class InterpolationSearch {

	public static void main(String[] args) {
		int [] arr= {1,3,9,12,14,17,24,28,29};
		int low = 0;
		int high = arr.length-1;
		int index = interpolationSearch(arr,low,high,17);
		System.out.print("所查找元素17的位置为："+index);
	}
	public static int interpolationSearch(int[] arr, int low, int high, int key) {
       
        if (low > high) {
            return -1;
        }
        int mid = low + (int) (1.0 * (key - arr[low]) / (arr[high] - arr[low]) * (high - low));
        if (mid < low || mid > high) {
            return -1;
        }
        if (arr[mid] == key) {
            return mid;
        } else if (key < arr[mid] ) {
            return interpolationSearch(arr,low,mid - 1,key);
        } else {
            return interpolationSearch(arr,mid + 1, high,key);
        }
    }

}

运行结果：

（2）方法二：迭代

public class InterpolationSearch {
	public static void main(String[] args) {
		int[] arr = { 1, 3, 9, 12, 14, 17, 24, 28, 29 };
		int index = insertvaluesearch(arr, 17);
		System.out.print("所查找元素17的位置为：" + index);
	}

	public static int insertvaluesearch(int arr[], int key) {
		int low = 0;
		int high = arr.length - 1;
		while (low <= high) {
			int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]);
			if (arr[mid] == key) {
				return mid;
			}
			if (arr[mid] < key) {
				low = mid + 1;
			}
			if (arr[mid] > key) {
				high = mid - 1;
			}
		}
		return -1;
	}

}

运行结果：