插值查找算法

插值查找算法：

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

插值查找注意事项：
对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快，关键字
分布不均匀的时候，该方法不必折半查找好。

代码实现：

public static int insertValueSearch(int[] arr,int left,int right,int findVal){
        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]);
        int midVal = arr[mid];
        if (findVal > midVal){//要查找的值大于中间值，所以应该向右递归
            insertValueSearch(arr,mid+1,right,findVal);
        }else if (findVal < midVal){//向左递归
            insertValueSearch(arr,left,mid-1,findVal);
        }else {
            return mid;
        }
        return mid;
    }