数据结构与算法（十六）插值查找算法

插值查找原理介绍:

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

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

• 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));

    }

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

插值查找注意事项：

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