插值查找

发布时间:2024年01月22日

概述

插值查找是一种在有序数组中查找给定值的算法。与二分查找类似,但是在定位中间元素时,插值查找不是简单地选取数组的中间元素,而是通过插值计算来确定一个更接近目标值的位置。

插值查找基于以下假设:数组中的元素是均匀分布的。也就是说,如果数组中有序元素的值差别很大,插值查找的效率可能会稍低。

基本思想:基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,差值查找也属于有序查找。

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

代码跟二分查找类似,只要修改一下mid的计算方式即可。

算法步骤

在这里插入图片描述

算法步骤如下:

  1. 确定要查找的目标值。

  2. 计算目标值在数组中的估计位置。插值查找使用一个公式来计算目标值的位置,通常是根据目标值与数组中最小和最大值的差异来计算。例如,如果目标值比最小值大一半,那么估计位置将在数组的一半位置。

     二分查找中查找点计算如下:
     
       mid=(low+high)/2, 即mid=low+1/2*(high-low);
     
     我们可以将查找的点改进为如下:
     
       mid=low+(key-a[low])/(a[high]-a[low])*(high-low),
     
     这样,让mid值的变化更靠近关键字key,这样也就间接地减少了比较次数。
    
  3. 比较估计位置处的值与目标值:

    • 如果值相等,返回估计位置。

    • 如果估计位置处的值比目标值大,说明目标值可能在数组的左侧,更新最大位置为估计位置的前一个位置,然后重复步骤2。

    • 如果估计位置处的值比目标值小,说明目标值可能在数组的右侧,更新最小位置为估计位置的后一个位置,然后重复步骤2。

  4. 重复步骤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方法来执行查找操作。如果找到目标值,则打印其索引;否则,打印目标值不存在于数组中的消息。

输出结果

在这里插入图片描述

文章来源:https://blog.csdn.net/kuxiaoyang/article/details/135756733
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。