基本思想： 基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下： mid=(low+high)/2, 即mid=low+1/2*(high-low);
通过类比，我们可以将查找的点改进为如下： mid=low+ (key-a[low])/(a[high]-a[low]) *(high-low)，
也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。
注： 对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
public class Cha { public static int Select(int[] arr, int value){ int mid; int low = 0; int high = arr.length - 1; while(low <= high){ //mid=(low+high)/2, 即mid=low+1/2*(high-low); mid = low+ (value-arr[low])/(arr[high]-arr[low]) *(high-low); if(arr[mid] < value){ low = mid + 1; } if(arr[mid] > value){ high = mid - 1; } if(arr[mid] == value) return mid; } return -1; } public static void main(String[] args) { int[] arr = {1,2,3,4,5,6,7,8,9}; System.out.println("2的下标为： " + Select(arr, 2)); } }