JAVA算法——插值查找

• 插值查找注意事项
• 插值查找算法原理介绍
• • 二分查找演变为插值查找

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

插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。将折半查找中的求mid索引公式，low表示左边索引left，high表示右边索引right，key就是二分查找讲的findVal

• 插值索引：int mid =low+(high-low)*(key-arr[low])/(arr[high]-arr[low])
• 对应left、right：mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left])

 # 代码实现
 
public class InsertValueSearch {
    public static void main(String[] args) {
        int [] arr = new int[100];
        for (int i =0;i<100;i++){
            arr[i]=i+1;
        }
        System.out.println(Arrays.toString(arr));
        int resultVal = insertValueSearch(arr,0, arr.length-1, 1);
        System.out.println(resultVal);
    }

    
    public static int insertValueSearch(int [] arr,int left,int right,int findVal){
        //当left>right时，说明递归整个数组，但是没有找到
        // findVal
        // findVal>arr[arr.length-1],说明查找的值比数组中最大的还大,因为数组是从小到大的有序数组。
        //在插值查找中findValarr[arr.length-1]条件必须有，因为findVal值参与插值索引公式计算，如果findVal不再数组中直接退出就好，否则可能会越界
        if (left>right || findValarr[arr.length-1]){
            return -1;
        }
        //求出mid
        int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
        int midVal = arr[mid];
        if (findVal>midVal){//说明应该向右边递归
            return insertValueSearch(arr,mid+1,right,findVal);
        }else if (findVal