Day569.插值查找 -数据结构和算法Java

类似二分查找，但找对应mid值的时候，采用的是自适应的方案

package com.achang.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;
        }

        System.out.println(insertValueSearch(arr, 0, arr.length-1, 55));
    }

    
    public static int insertValueSearch(int[] arr,int left,int right,int findValue){
        if (left > right ||  findValue < arr[0] || findValue > arr[arr.length-1]) return  -1;

        //求出mid，插值查找中自适应mid
        int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);
        int midValue = arr[mid];
        if (findValue > midValue){
            return insertValueSearch(arr,mid+1,right,findValue);//向右递归
        }else if (findValue < midValue){
            return insertValueSearch(arr,left,mid-1,findValue);//向左边递归
        }else {
            return mid;
        }
    }
}