插值查找算法

简介: 插值查找算法又称插值搜索算法,是在二分查找算法的基础上改进得到的一种查找算法。

java实现插值查找算法


插值查找算法原理介绍:
1.插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。

2.将折半查找中的求mid索引的公式进行优化,key 代表查找的值findValue

公式为:int midIndex = left + (right- left ) * (key - arr[left ]) / (arr[right]- arr[left ]);

对应代码:int mid=left +(right-left)*(findval-arr[left])/(arr[right]-arr[left]);


插值查找注意事项
在元素数值均匀分布的有序数组里面, 用这种方法查找是很快的。特别的,对绝对均匀分布的数组(相邻元素差值相同), 插值查找用一次比较就能查找成功:

当然了, 前提是数组中元素数值是均匀分布的, 如果是对 1,2,40,99,1000 这种分布很不均匀的数组, 插值查找的计算会起到反效果, 就不如二分查找了

时间复杂度:O(logn)



java代码实现

//插值查找算法,也要求是有序的。
public class InsertValueSearch {
    public static void main(String[] args) {

        int[] arr = {0, 10, 20, 21, 23, 56, 75, 99, 100};
        int result = insertValueSearch(arr, 0, arr.length - 1, 99);

        if (result != -1) {
            System.out.println("结果为:" + result);
        } else {
            System.out.println("没有找到对应的结果。");
        }

    }

    /**
     * 插值查找算法
     *
     * @param arr     待查找的数组
     * @param left    待查找数组的左边
     * @param right   待查找数组的右边
     * @param findval 带查找的数
     * @return 若找到就返回 对应的下标,若没有找到就返回-1.
     */
    public static int insertValueSearch(int[] arr, int left, int right, int findval) {
        if (left > right || findval < arr[0] || findval > arr[arr.length - 1]) {
            return -1;
        }

        int mid = left + (right - left) * (findval - arr[left]) / (arr[right] - arr[left]);
        int find = arr[mid];
        if (findval < find) {
            return insertValueSearch(arr, left, mid - 1, findval);
        } else if (findval > find) {
            return insertValueSearch(arr, mid + 1, right, findval);
        } else {
            return mid;
        }

    }

}
目录
相关文章
|
5月前
|
算法 计算机视觉
图像处理之三种常见双立方插值算法
图像处理之三种常见双立方插值算法
36 2
|
5月前
|
算法 C语言 计算机视觉
图像处理之图像快速插值放缩算法
图像处理之图像快速插值放缩算法
35 0
|
6月前
|
编解码 算法 计算机视觉
基于FPGA的图像最近邻插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
基于FPGA的图像最近邻插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
|
6月前
|
算法 计算机视觉 Python
python 插值算法
最近在做时间序列预测时,在突增或者突降的变化剧烈的情况下,拟合参数的效果不好,有用到插值的算法补全一些数据来平滑剧烈变化过程。还有在图像处理中,也经常有用到插值算法来改变图像的大小,在图像超分(Image Super-Resolution)中上采样也有插值的身影【2月更文挑战第8天】
79 2
|
6月前
|
算法
MATLAB | 插值算法 | 一维interpl插值法 | 附数据和出图代码 | 直接上手
MATLAB | 插值算法 | 一维interpl插值法 | 附数据和出图代码 | 直接上手
216 0
|
6月前
|
算法
MATLAB | 插值算法 | 二维griddata插值法 | 附数据和出图代码 | 直接上手
MATLAB | 插值算法 | 二维griddata插值法 | 附数据和出图代码 | 直接上手
465 0
|
6月前
|
算法
MATLAB | 插值算法 | 一维Lagrange插值法 | 附数据和出图代码 | 直接上手
MATLAB | 插值算法 | 一维Lagrange插值法 | 附数据和出图代码 | 直接上手
189 0
|
11月前
|
算法 数据处理
数据拟合、参数估计、插值等数据处理算法
数据拟合、参数估计、插值等数据处理算法
138 0
数据拟合、参数估计、插值等数据处理算法
|
6月前
|
算法
【MATLAB】史上最全的5种数据插值算法全家桶
【MATLAB】史上最全的5种数据插值算法全家桶
103 0
基于亚奈奎斯特采样和SOMP算法的平板脉冲响应空间插值matlab仿真
基于亚奈奎斯特采样和SOMP算法的平板脉冲响应空间插值matlab仿真