Java版插值查找

分析&回答

/**
 * 插值查找
 * <p>
 * 插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。
 * <p>
 * 自适应 计算自适应mid
 * int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])
 *
 * @param arr
 * @param left
 * @param right
 * @param target
 * @return
 */
public static int insertValueSearch(int[] arr, int left, int right, int target) {
    if (left > right || target < arr[0] || target > arr[arr.length - 1]) {
        return -1;
    }
    int mid = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left]);
    if (target > arr[mid]) {
        return insertValueSearch(arr, mid + 1, right, target);
    } else if (target < arr[mid]) {
        return insertValueSearch(arr, left, mid - 1, target);
    } else {
        return mid;
    }
}

public static void main(String[] args) {
    // index     0  1  2  3  4  5  6  7  8  9  10
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    int target = 5;
    InsertValueSearch demo = new InsertValueSearch();
    System.out.println("Find index in: " + demo.insertValueSearch(arr, 0, arr.length - 1, target));
}

反思&扩展

• 查找条件：有序数组
• 平均时间复杂度O(㏒(㏒n))
• 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.
• 关键字分布不均匀的情况下，该方法不一定比折半查找要好