@SuppressWarnings("all")
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for(int i = 1;i <= 100;i ++){
            arr[(i - 1)] += i;
        }
        System.out.println(insertValuesearch(arr,0,arr.length - 1,100));
    }

    /**
     * @param arr 数组
     * @param left 左边索引
     * @param right 右边索引
     * @param value 查找值
     * @return 如果找到，返回对应下标，没有返回 -1
     */
    public static int insertValuesearch(int[] arr,int left,int right,int value){
        /**
         * 注意：value < arr[0] 和 value > arr[arr.length - 1] 必须需要
         * 否则我们得到的mid可能越界
         * arr.length - 1 < right 判断传入的right值是否大于了传入数组的长度
         */
        if(left > right || value < arr[0] || value > arr[arr.length - 1] || arr.length - 1 < right){
            return -1;
        }

        //求mid的值 称为自适应写法
        int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);

        int midVal = arr[mid];

        if (value > midVal) {
            //向右边递归
            return insertValuesearch(arr,mid + 1,right,value);
        }else if(value < midVal) {
            //向左边递归
            return insertValuesearch(arr,left,mid - 1,value);
        }else{
            return mid;
        }
    }
}