插值查找算法

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

代码

package com.search;

public class InsertValueSearch {
    public static void main(String[] args) {
//        int[] arr = new int[100];
//        for(int i=0;i<arr.length;i++){
//            arr[i] = i+1;
//        }
        //用两个不同的数组来测试，一个是分布均匀的，一个是不均匀的。
        int[] arr = {1,8,10,89,1000,1000,1000,1234};
        int i = insertValueSearch(arr, 0, arr.length - 1, 89);
        System.out.println(i);
    }

    //插值查找算法也需要数组是有序数组
    public static int insertValueSearch(int[] arr,int left,int right,int target){
        System.out.println("hello");//用来查看进行几次递归
        if(left > right || arr[left]>target || arr[right]<target){
            return -1;
        }

        int mid = left + (right - left)*(target - arr[left])/(arr[right] - arr[left]);
        int midVal = arr[mid];
        if (midVal > target){
            return insertValueSearch(arr,left,mid-1,target);
        }else if(midVal < target){
            return insertValueSearch(arr,mid+1,right,target);
        }else{
            return mid;
        }
    }

}