插值查找算法

介绍

插值查找（Insert Value Search）是二分查找的一种改良，主要是改良了mid的值，mid的值由原来的mid = (left + right) / 2而变成了自适应获取mid的值mid = left + (num - arr[left]) / (arr[right] - arr[left]) * (right - left)，上述公式是前辈们推导出来的，其余和二分查找一样。

对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快。而关键字分布不均匀的情况下，该方法不一定比二分查找要好。

public static int insertValueSearch(int[] arr, int num) {
    return insertValueSearch(arr, 0, arr.length - 1, num);
}

public static int insertValueSearch(int[] arr, int left, int right, int num) {
    //如果没有找到
    if (left > right || num < arr[0] || num > arr[arr.length - 1]) {
        return -1;
    }
    //获取中间索引
    int mid = left + (num - arr[left]) / (arr[right] - arr[left]) * (right - left);
    //往左边递归找
    if (num < arr[mid]) {
        return insertValueSearch(arr, left, mid - 1, num);
    }
    //往右边递归找
    else if (num > arr[mid]) {
        return insertValueSearch(arr, mid + 1, right, num);
    }
    //数据位置找到
    else {
        return mid;
    }
}