插值查找算法详解及优化

插值查找

插值查找，有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找，将查找点的选择改进为自适应选择，提高查找效率。

自适应选择点：

int mid=left+(findVal-arr[left])*(right-left)/(arr[right]-arr[left]);

>>思路：
定义很明显就是基于二分查找，所以直接搬
问题就在于这个自适应选择
自适应选择点： ` int mid=left+(findVal-arr[left])*(right-left)/(arr[right]-arr[left]);`
  解释：首先给大家解释一下，传入的数组是有序的，这点很重要；
                          这里用到比例相等；
                          
                      (findVal-arr[left])       (arr[right]-arr[left])
                      ————————————————————  =   ——————————————————————
                      findVal的下标-left              right-left
                      
         化简得到：findVal的下标=left+(findVal-arr[left])*(right-left)/(arr[right]-arr[left])
  因为我们的自适应点，已经很接近findVal的下标，所以能更快的找出对应的值

>>注意:
因为我们的寻找的点是随机的，但是我们的自适应点又是受寻找点的影响的
所以，我们要将不在范围内的数，直接返回找不到
           

代码：（只能查找出来一个下标）

public static void insertValuesSearch(int[] arr,int left,int right,int findVal) {
        //出口：因为传入的数组是有序的，所以，可以限制搜索值
        if (left>right||findVal<arr[left]||findVal>arr[right]){
            System.out.println("未找到");
            return;
        }
        //由于mid的值受到了搜索值的影响，所以要在出口处防止搜索值的逾越
        int mid=left+(findVal-arr[left])*(right-left)/(arr[right]-arr[left]);
        if (findVal>arr[mid]){
            insertValuesSearch(arr, mid+1, right, findVal);
        }else if(findVal<arr[mid]){
            insertValuesSearch(arr, left, mid-1, findVal);
        }else {
            System.out.println("下标为："+mid);
        }
    }
           

优化代码：（可以查找出来所有下标）

public static void insertValuesSearchOpt(int[] arr,int left,int right,int findVal) {
        //出口：因为传入的数组是有序的，所以，可以限制搜索值
        if (left>right||findVal<arr[left]||findVal>arr[right]){
            System.out.println("未找到");
            return;
        }
        //由于mid的值受到了搜索值的影响，所以要在出口处防止搜索值的逾越
        int mid=left+(findVal-arr[left])*(right-left)/(arr[right]-arr[left]);
        if (findVal>arr[mid]){
            insertValuesSearchOpt(arr, mid+1, right, findVal);
        }else if(findVal<arr[mid]){
            insertValuesSearchOpt(arr, left, mid-1, findVal);
        }else {
            //找到因为数组的有序性，所以向前找可以找到第一个满足待查值的下标
            int start=0;
            while (mid>=0&&arr[mid]==findVal) {//防止mid越界
                start=mid;
                mid--;
            }
            //从第一个满足值的下标向后遍历直到不满足
            while (start<arr.length&&arr[start]==findVal){
                System.out.println("下标为："+start);
                start++;
            }
        }
    }