查找算法----插值查找

1. 插值查找：在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不 会从中间开始查起，而是有一定目的的往前或往后翻。同样的，比如要在取值范围1~10000之间100个元素从小到大均匀分布的数组中查找5，我们自然会考虑从。数组下标较小的开始查找。
        经过以上分析，折半查找这种查找方式，不是自适应的(也就是说是傻瓜式的)。二分查找中查找点计算如下：mid = (low + high ) / 2，即mid = low + 1 / 2 * ( high - low )。
        通过类比，我们可以将查找的点改进为如下：mid = low + ( key-a[low] ) / ( a[high]-a[low] ) = ( high-low )。     

2. 插值查找的的时间复杂度：插值查找的的时间复杂度为O( log( logn ) )。                                    

3. 插值查找的要点：

       1>.对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

        2>.插值查找也同样只适用于有序的的数据结构中。

4. 插值查找的实现：

//插值查找
/*
 * 类似于二分查找 但是差值查找的mid的值 通过一定算法计算得来 而不是二分
 * 但是数组的数据也必须的有序的
 * 如果数组数据的分布方差较为均匀 则更适合用差值查找
 * 如果数组数据的分布方差较大 则不适合用差值查找 可以考虑其他查找方法
 */
public class InterpolationSearch {
	public static void main(String[] args) {
		int[] arr = {-10, -5, 0, 4, 8, 13, 45, 56, 67, 78, 99, 104};

        //递归的方式实现插值查找
		int index = interpolationSearch(arr, 0, arr.length - 1, 13);
		if(index != -1) {
			System.out.println("递归方式查找的元素在数组中下标：" + index + "的位置");
		}else {
			System.out.println("递归方式没有找到要查找的元素");
		}

        //迭代的方式实现插值查找
        int index1 = interpolationSearch(arr, 13);
		if(index1 != -1) {
			System.out.println("迭代方式查找的元素在数组中下标：" + index1 + "的位置");
		}else {
			System.out.println("迭代方式没有找到要查找的元素");
		}
	}

	/*
	 * 对数据进行插值查找 递归的方式
	 * low表示当前数组的最小值的索引
	 * high表示当前数组的最大值的索引
	 * key表示要查找的元素
	 */
	private static int interpolationSearch(int[] arr, int low, int high, int key) {
		//递归临界条件 当low大于high时 则表示要查找的元素不在数组中
		if(low > high) { 
			return -1;
		}
		
		//计算mid
		/*
		 * (key - arr[low]) / (arr[high] - arr[low]) 比例不能取整 因为正常情况下该比例都是
		 * 小于1的 如果取整就是会是0 因此要将该比例转换为小数 最后在转为整型即可
		 */
		int mid = low + (int) (1.0 * (key - arr[low]) / (arr[high] - arr[low]) * (high - low));
		
		//如果mid小于low 或者 mid大于high 则表示要查找的元素不在数组中
		if(mid < low || mid > high) { 
			return -1;
		}
		
		/*
		 * 如果mid位置的值等于key 则表示找到了指定元素 返回其索引即可
		 * 如果mid位置的值大于key 则表示要查找的元素位于mid的左边 
		 * 继续向下递归 查找的范围为：从low到mid-1
		 * 如果mid位置的值小于key 则表示要查找的元素位于mid的右边 
		 * 继续向下递归 查找的范围为：从mid+1到high
		 */
		if(arr[mid] == key) {
			return mid;
		}else if(arr[mid] > key) {
			return interpolationSearch(arr, low, mid - 1, key);
		}else {
			return interpolationSearch(arr, mid + 1, high, key);
		}
	}


    //迭代的方式实现插值查找 key为要查找的元素
	private static int interpolationSearch(int[] arr, int key) {
		int low = 0;
		int high = arr.length - 1;
		int mid = low + (int)(1.0 * (key - arr[low]) / (arr[high] - arr[low]) * (high - low));
		while(arr[mid] != key) {
			if(arr[mid] > key) {
				high = mid - 1;
			}else if(arr[mid] < key){
				low = mid + 1;
			}
			if(low > high) {
				return -1;
			}
			mid = low + (int)(1.0 * (key - arr[low]) / (arr[high] - arr[low]) * (high - low));
			if(mid < low || mid > high) {
				return -1;
			}
		}
		return mid;
	}
}

4. 运行结果：