/**
 * @Auther: Arsenal
 * @Date: 2020-03-22 23:29
 * @Description: 插值查找
 */
public class InterpolationSearch {
    public static void main(String[] args) {

        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i;
        }

        //int resIndex = recusionInterpolationSearch(arr, 0, arr.length - 1, 0);
        int resIndex = interpolationSearch(arr, 0, arr.length - 1, 50);
        System.out.println("resIndex:" + resIndex);
    }

    /**
     * 插值查找
     * @param arr  需查询的数组
     * @param low  左下标
     * @param high 右下标
     * @param key  需查找的值
     * @return 找到返回下标，否找返回-1
     */
    public static int interpolationSearch(int[] arr, int low, int high, int key) {

        while (low <= high) {
            //公式自适应，提供查询效率
            int mid = low + (key - arr[low]) / (arr[high] - arr[low]) * (high - low);

            if (arr[mid] > key) {
                high = mid - 1;
            } else if (arr[mid] < key) {
                low = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

    /**
     * 递归插值查找
     * @param arr  需查询的数组
     * @param low  左下标
     * @param high 右下标
     * @param key  需查找的值
     * @return 找到返回下标，否找返回-1
     */
    public static int recusionInterpolationSearch(int[] arr, int low, int high, int key) {
        System.out.println("hello");
        //注意：key < arr[0]  和  key > arr[arr.length - 1] 必须需要
        //否则我们得到的 mid 可能越界
        if (low > high || key < arr[0] || key > arr[arr.length - 1]) {
            return -1;
        }

        //公式自适应，提供查询效率
        int mid = low + (key - arr[low]) / (arr[high] - arr[low]) * (high - low);
        //int mid = (high + low) / 2;

        if (arr[mid] > key) { //向左递归
            return recusionInterpolationSearch(arr, low, mid - 1, key);
        } else if (arr[mid] < key) { //向右递归
            return recusionInterpolationSearch(arr, mid + 1, high, key);
        } else {
            return mid;
        }
    }
}