插值查找

二分查找效率很高，查找的时候每次都要和中间值比较，如果和数组 1/4 或者 3/4 部分的值比较可不可以呢？对于一个要查找的数不知道他大概在数组什么位置的时候可以使用二分查找。但如果我们知道要查找的值大概在数组的最前面或最后面的时候可以使用插值查找。比如查字典的时候如果是 a 或者 b 开头的一般会在前面找，如果是 y 或者 z 开头的一般偏向于往后面找。二分法查找比较的是中间值，但插值查找比较的不是中间值，他是根据目标值在查找区间内的百分比确定需要比较的值，如下图所示。

来看下插值查找的代码。

public int search(int[] nums, int target) {
    int left = 0;// 查找的左边界。
    int right = nums.length - 1;// 查找的右边界
    while (left <= right) {// 有效区间内继续查找。

        // 防止插值查找的时候除数为 0 ，需要提前判断下。
        if (nums[right] == nums[left])
            return nums[right] == target ? left : -1;

        // 和二分法不同的地方在这，这要注意乘的时候出现溢出，可以先转为long类型。
        int mid = left + (right - left) * (target - nums[left]) / (nums[right] - nums[left]);
        if (target == nums[mid])// 如果找到直接返回。
            return mid;
        else if (target < nums[mid])// 如果查找的值小于中间元素，缩小右边界。
            right = mid - 1;
        else
            left = mid + 1;// 如果查找的值大于中间元素，缩小左边界。
    }
    return -1;// 没找到，返回 -1 。
}

再来看下递归的写法。

public int search(int[] nums, int target) {
    return helper(nums, target, 0, nums.length - 1);
}

private int helper(int[] nums, int target, int left, int right) {
    if (left > right)
        return -1;
    if (nums[right] == nums[left]) return nums[right] == target ? left : -1;
    // 和二分法不同的地方在这。
    int mid = left + (right - left) * (target - nums[left]) / (nums[right] - nums[left]);
    if (target == nums[mid])
        return mid;// 找到直接返回。
    else if (target < nums[mid])
        return helper(nums, target, left, mid - 1);// 在左边部分查找。
    else return helper(nums, target, mid + 1, right);// 在右边部分查找。
}

其实他和二分查找非常相似，唯一的区别就是计算 mid 的时候不同。