package com.xcc.dataStructures.demo07_search;

/**
 * 插值查找
 *
 * @author xiaocheng
 * @date 2020/12/9 11:08
 */
public class InsertValSearch {

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 8, 9, 11, 13, 15};
        int index = insertValSearch(arr, 0, arr.length -1 , 8);
        System.out.println(index);
    }

    public static int insertValSearch(int[] arr,int left , int right,int val) {
        System.out.println("插值查找~~");
        if (left > right || arr[left] > val || arr[right] < val) {
            return -1;
        }
        int mid = left + (right - left) * (val - arr[left]) / (arr[right] - arr[left]);
        if (val > arr[mid]) {
            return insertValSearch(arr, mid + 1, right, val);
        } else if (val < arr[mid]) {
            return insertValSearch(arr, left, mid - 1, val);
        }else {
            return mid;
        }
    }

}