插值搜索的Java实现
原理说明：
插值查找，有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找，将查找点的选择改进为自适应选择，提高查找效率。
插值类似于平常查英文字典的方法，在查一个以字母C开头的英文单词时，决不会用二分查找，从字典的中间一页开始，因为知道它的大概位置是在字典的较前面的部分，因此可以从前面的某处查起，这就是插值查找的基本思想。
比如我们要查找数字6，过程如下图所示：
插值查找性能：算法在最好和最坏情况下的关键字比较次数是明显的，但平均情况的分析比较复杂，并且这里的“平均”与前面讨论过的查找算法的平均不同，这里是在元素满足某种分布情况下的平均。
优缺点：
1、对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快。
2、关键字分布不均匀的情况下，该方法不一定比折半查找要好。
实例源码：
源代码：
执行
执行中...
x
1
public class Interpolation_Search 2
3
{//N o w J a v a . c o m - 时代Java 提供4
5
public static int interpolation(int a[], int n, int search_item) // Function implementing Interpolation_Search6
7
{8
9
int high = n-1;10
11
int low = 0;12
13
int pos;14
15
16
while(low <= high && search_item >= a[low] && search_item <= a[high])17
18
{19
20
int rise = high - low;21
22
int run = a[high] - a[low];23
24
int x = search_item - a[low];25
26
pos = low + (rise / run) * x;27
28
29
if(a[pos] == search_item)30
/** from 31
时 代 J a v a - nowjava.com**/32
33
return pos;34
35
else if(search_item < a[pos])36
37
high = pos - 1;38
39
else if(search_item > a[pos])40
41
low = pos + 1;42
43
}44
45
46
return -1;47
48
}49
50
51
// Driver Function52
53
public static void main(String[] args)54
55
{56
57
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // Sorted Input array58
59
int n = a.length; // Size of array60
61
int search_item = 8; // Element to be searched62
63
/**代码未完, 请加载全部代码(NowJava.com).**/执行结果：
本文系作者在时代Java发表，未经许可，不得转载。如有侵权，请联系nowjava@qq.com删除。
编辑于
关注时代Java