数据结构与算法(十六)插值查找算法

插值查找原理介绍:

  • 插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。

  • 将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right. key 就是前面我们讲的 findVal
    image.png

  • int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;/插值索引/ 对应前面的代码公式:
    int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])

代码实现

 /**
     * 插值查找
     * @param arr
     * @param left
     * @param right
     * @param findVal
     * @return
     */
    public static int insertValueSearch(int [] arr,int left ,int right,int findVal){
        System.out.println("插值查找");
        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]);
        if (arr[mid]>findVal){
            return  insertValueSearch(arr,left,mid-1,findVal);
        }else if (arr[mid]<findVal){
            return  insertValueSearch(arr,mid+1,right,findVal);
        }else {

            return mid;
        }
    }

我们比较下合二分法的效率

public static void main(String[] args) {

        //原数据
        int [] arr={1,2,3,4,5,6,7,8,9};
        //插值查找
        System.out.println(insertValueSearch(arr,0,arr.length-1,1));
        //二分法查找
        System.out.println(BinarySearch.binarySearch(arr,0,arr.length-1,1));

    }

image.png

我们看到在这次的实验中,二分法查询了3次,而插值方法,只查询了一次。

插值查找注意事项:

对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找, 速度较快.
关键字分布不均匀的情况下,该方法不一定比折半查找要好

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://www.fengpt.cn/archives/数据结构与算法十六插值查找算法