插值查找算法

java实现插值查找算法

插值查找算法原理介绍:
1.插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。

2.将折半查找中的求mid索引的公式进行优化，key 代表查找的值findValue

公式为：int midIndex = left + (right- left ) * (key - arr[left ]) / (arr[right]- arr[left ]);

对应代码：int mid=left +(right-left)*(findval-arr[left])/(arr[right]-arr[left]);

插值查找注意事项
在元素数值均匀分布的有序数组里面， 用这种方法查找是很快的。特别的，对绝对均匀分布的数组（相邻元素差值相同）， 插值查找用一次比较就能查找成功：

当然了， 前提是数组中元素数值是均匀分布的， 如果是对 1,2,40,99,1000 这种分布很不均匀的数组， 插值查找的计算会起到反效果， 就不如二分查找了

时间复杂度：O(logn)

java代码实现

//插值查找算法，也要求是有序的。
public class InsertValueSearch {
    public static void main(String[] args) {

        int[] arr = {0, 10, 20, 21, 23, 56, 75, 99, 100};
        int result = insertValueSearch(arr, 0, arr.length - 1, 99);

        if (result != -1) {
            System.out.println("结果为：" + result);
        } else {
            System.out.println("没有找到对应的结果。");
        }

    }

    /**
     * 插值查找算法
     *
     * @param arr     待查找的数组
     * @param left    待查找数组的左边
     * @param right   待查找数组的右边
     * @param findval 带查找的数
     * @return 若找到就返回 对应的下标，若没有找到就返回-1.
     */
    public static int insertValueSearch(int[] arr, int left, int right, int findval) {
        if (left > right || findval < arr[0] || findval > arr[arr.length - 1]) {
            return -1;
        }

        int mid = left + (right - left) * (findval - arr[left]) / (arr[right] - arr[left]);
        int find = arr[mid];
        if (findval < find) {
            return insertValueSearch(arr, left, mid - 1, findval);
        } else if (findval > find) {
            return insertValueSearch(arr, mid + 1, right, findval);
        } else {
            return mid;
        }

    }

}