插值查找是一种在有序数组中查找给定值的算法。与二分查找类似,但是在定位中间元素时,插值查找不是简单地选取数组的中间元素,而是通过插值计算来确定一个更接近目标值的位置。
插值查找基于以下假设:数组中的元素是均匀分布的。也就是说,如果数组中有序元素的值差别很大,插值查找的效率可能会稍低。
基本思想:基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,差值查找也属于有序查找。
细节: 对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择。
代码跟二分查找类似,只要修改一下mid的计算方式即可。
算法步骤如下:
确定要查找的目标值。
计算目标值在数组中的估计位置。插值查找使用一个公式来计算目标值的位置,通常是根据目标值与数组中最小和最大值的差异来计算。例如,如果目标值比最小值大一半,那么估计位置将在数组的一半位置。
二分查找中查找点计算如下:
mid=(low+high)/2, 即mid=low+1/2*(high-low);
我们可以将查找的点改进为如下:
mid=low+(key-a[low])/(a[high]-a[low])*(high-low),
这样,让mid值的变化更靠近关键字key,这样也就间接地减少了比较次数。
比较估计位置处的值与目标值:
如果值相等,返回估计位置。
如果估计位置处的值比目标值大,说明目标值可能在数组的左侧,更新最大位置为估计位置的前一个位置,然后重复步骤2。
如果估计位置处的值比目标值小,说明目标值可能在数组的右侧,更新最小位置为估计位置的后一个位置,然后重复步骤2。
重复步骤3,直到找到目标值或确定目标值不存在于数组中。
插值查找的时间复杂度为O(log log N),其中N是数组的大小。虽然在大多数情况下表现良好,但是当元素分布不均匀时,插值查找算法的性能可能会下降,并可能退化为线性搜索。
需求:定义一个方法利用插值查找,数据如下:{2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
要求:查询某个元素是否存在
代码示例:
package text.text02;
/*
插值查找
插值查找是一种在有序数组中查找给定值的算法。
前提:数组中的元素是均匀分布的
mid=low+(key-a[low])/(a[high]-a[low])*(high-low)
*/
public class text08A {
public static void main(String[] args) {
int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
//定义两个要查询的数(一个能查到,一个查不到)
int target1 = 23;
int target2 = 48;
//调用interpolationSearch方法
int result1 = interpolationSearch(arr, target1);
int result2 = interpolationSearch(arr, target2);
//调用judge方法,并将interpolationSearch方法的返回值和要查找的数作为参数
judge(result1, target1); //23存在数组中,其索引为:5
judge(result2, target2); //48不存在于数组中
}
public static int interpolationSearch(int[] arr, int target) {
//定义变量记录数组的初始索引
int low = 0;
//定义变量记录数组长度-1,即数组的最大索引
int high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
//最小索引等于最大索引时
if (low == high) {
//最小索引或者最大索引处的值等于要查找的值
if (arr[low] == target) {
//返回该索引
return low;
}
//返回-1,表示没找到
return -1;
}
// 计算估计位置
int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);
//中间索引处的值等于要查找的值
if (arr[pos] == target) {
return pos;
}
//中间的数小于要查找的数,说明要查找的数在中间的数的右边
if (arr[pos] < target) {
//让最小的索引变为中间索引+1
low = pos + 1;
}
//中间的数大于要查找的数,说明要查找的数在中间的数的左边
else {
//让最大索引变为中间索引-1
high = pos - 1;
}
}
//返回-1,表示没找到
return -1;
}
//定义一个方法根据interpolationSearch方法的返回值判断
public static void judge(int index, int number) {
if (index == -1) {
System.out.println(number + "不存在于数组中");
} else {
System.out.println(number + "存在数组中,其索引为:" + index);
}
}
}
在这个示例中,我们定义了一个名为
interpolationSearch
的静态方法,接受一个有序整数数组arr
和要查找的目标值target
作为参数。在方法内部,我们使用一个while循环进行迭代查找。
在每一次迭代中,我们首先检查目标值是否在数组的范围内。如果不在范围内,则表示目标值不存在于数组中,返回-1。
然后,我们通过插值计算来获取目标值的估计位置
pos
。接下来,我们根据估计位置处的值与目标值的比较结果进行相应的操作。
最后,我们在
main
方法中定义了一个示例数组arr
和要查找的目标值target
,并调用interpolationSearch
方法来执行查找操作。如果找到目标值,则打印其索引;否则,打印目标值不存在于数组中的消息。