拉格朗日插值查找算法

谁借莪１个温暖的怀抱￠ 2023-02-20 04:53 45阅读 0赞

> 插值查找是对二分查找的一种改进，适用于均匀分布的有序表

# 算法思想 #

插值查找其实是折半查找的升级版，在我们写折半查找的时候不知道大家想过没有为什么每次要折一半呢？1/4不行吗？1/8不行吗？这样我们就可以想到，是不是可以找到更精准的“折半”的方式来处理呢。

肯定是可以的，比如说找字典的时候，找a这个字母，我们肯定不会从中间开始，而是偏向于字典前面一些开始。

在折半查找中 ：  
![在这里插入图片描述][2020062313514288.png]

我们可以看到 “(high-low)”的系数为1/2，但是我们想找一个自适应的系数以便于找到目标数与下标为mid所对应的数更加的接近，我们就要将这个系数更改掉，让程序自己去找与目标数更加接近的数。

我们对1/2进行改进:  
![在这里插入图片描述][20200623135318658.png]

简单的理解就是计算出key所占比，然后更好地找到key所在的区间范围  
但是对于极端分布的数组，插值查找的效率就大打折扣了  
比如a\[7\]=\{0,1,2,100,102,1000,10000\}

# 代码 #

**适用场景：目标已经有序而且分布均匀**

## java实现 ##

public class TreeNode {
        
        private static int InsertionSearch(int[] arr, int key){
        
            if (arr == null){
        
                return -1;
            }
    
            int low = 0;
            int high = arr.length - 1;
            while (low <= high){
        
                //找出预测数组中的位置
                int mid = low +  (high - low) * (key - arr[low])/(arr[high] - arr[low]);
                if (arr[mid] == key){
        
                    return mid;
                }else if (arr[mid] > key){
        
                    high = mid - 1;
                }else{
        
                    low = mid + 1;
                }
            }
    
            return -1;
        }
    
    
    
        public static void main(String[] args) {
        
            int arr[] = {
        1,2,5,7,11,14,16,17,20,22,25,28,30,33,35,38,40,42,46,50,53,57,58,60};
    
            int index= InsertionSearch(arr, 25);
            if (index == -1){
        
                System.out.println("找不到");
            }else{
        
                System.out.println("索引" + index + "值为" + arr[index]);
            }
        }
    }

在元素数值均匀分布的有序数组里面， 用这种方法查找是很快的。特别的，对绝对均匀分布的数组（相邻元素差值相同）， 插值查找用一次比较就能查找成功：

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

**时间复杂度平均为：O(logn)**

[参考][Link 1]  
[参考][Link 2]

[2020062313514288.png]: https://img-blog.csdnimg.cn/2020062313514288.png
[20200623135318658.png]: https://img-blog.csdnimg.cn/20200623135318658.png
[Link 1]: https://www.cnblogs.com/CJT-blog/p/10475707.html
[Link 2]: https://segmentfault.com/a/1190000022435598