差值查找算法与二分查找算法类似,主要就是mid的值不是(left=right)/2,而是mid=low+(high-low)*(key-arr[low])/(arr[high]-arr[low]);

其中有两点不同:

1,int mid=low+ (right-left) * (findVal-arr[left]) / (arr[right] - arr[left])

2,由于mid公式里面自适应加入了findVal,所以我们前面要加判断findVal<arr[left]和findVal>arr[right]

代码实现如下:

 public static List<Integer> insertValueSearch(int[] arr,int left,int right,int findVal){
        if (left>right || findVal<arr[left] || findVal>arr[right]){
            return new ArrayList();
        }

        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<midVal){
          return   insertValueSearch(arr,left,mid-1,findVal);
        }else{
            List<Integer> list=new ArrayList<Integer>();
            int temp=mid-1;
            while (true){
                if (temp<0||arr[temp]!=findVal){
                    break;
                }
                list.add(temp);
                temp--;
            }
            list.add(mid);
            temp=mid+1;
            while (true){
                if (temp>arr.length-1 ||arr[temp]!=findVal){
                    break;
                }
                list.add(temp);
                temp+=1;
            }
            return list;
        }
    }

注意:

• 对于数据量较大，关键字分布比较均匀（最好是线性分布）的查找表来说，采用插值查找，速度较快
• 关键字分布不均匀的情况下， 该方法不一定比折半查找要好
• 查找的数组是有序数组