插值查找的实现与总结(Java)

插值查找算法

插值查找原理介绍：

• 插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。

公式推导：

代码实现：

package com.athome.search;

/**
 * Description:
 * Author:江洋大盗
 * Date:2021/1/21 18:48
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        //测试非递归插值查找
        int i1 = insertValueSearch(arr, 10);
        System.out.println("非递归插值查找:" + i1);
        //测试递归插值查找
        int i2 = insertValueSearch(arr, 8, 0, arr.length - 1);
        System.out.println("递归插值查找:" + i2);
    }

    /**
     * 非递归插值查找
     *
     * @param arr    待查找数据的数组，此处默认数组使用从小到大的顺序排列
     * @param target 查找的目标值
     * @return 返回要查找值的下标，若查询不到返回-1
     */
    public static int insertValueSearch(int[] arr, int target) {
        if (target < arr[0] || target > arr[arr.length - 1]) {
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left]);
            if (target < arr[mid]) {
                right = mid - 1;
            } else if (target > arr[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 递归插值查找
     *
     * @param arr    待查询数据的数组
     * @param target 目标值
     * @param left   左角标
     * @param right  右角标
     * @return 返回要查找值的下标，若查询不到返回-1
     */
    public static int insertValueSearch(int[] arr, int target, int left, int right) {
        if (left > right || target < arr[0] || target > arr[arr.length - 1]) {
            return -1;
        }
        int mid = left + (target - arr[left]) * (arr[right] - arr[left]) / (right - left);
        if (target < arr[mid]) {
            return insertValueSearch(arr, target, left, mid - 1);
        } else if (target > arr[mid]) {
            return insertValueSearch(arr, target, mid + 1, right);
        } else {
            return mid;
        }
    }
}

结语

只要能收获甜蜜，荆棘丛中也有蜜蜂忙碌的身影，未来的你一定会感谢现在努力的自己。