插值搜索的Java实现

原理说明：

插值查找，有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找，将查找点的选择改进为自适应选择，提高查找效率。
插值类似于平常查英文字典的方法，在查一个以字母C开头的英文单词时，决不会用二分查找，从字典的中间一页开始，因为知道它的大概位置是在字典的较前面的部分，因此可以从前面的某处查起，这就是插值查找的基本思想。

比如我们要查找数字6，过程如下图所示：

插值查找性能：算法在最好和最坏情况下的关键字比较次数是明显的，但平均情况的分析比较复杂，并且这里的“平均”与前面讨论过的查找算法的平均不同，这里是在元素满足某种分布情况下的平均。

优缺点：
1、对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快。
2、关键字分布不均匀的情况下，该方法不一定比折半查找要好。