java实现数据查找算法:插值查找

今天爱分享给大家带来java实现数据查找算法:插值查找,希望大家能够喜欢。

1,插值查找基本介绍
插值查找的前提条件是目标数组为有序数组
插值查找类似于二分查找,不同的是插值查找每次从自适应middle索引开始查找
插值查找其实就是对二分查找middle索引求值的优化,求值公式为:

int middle = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left])

二分查找到插值查找的公式演进如下:

举例说明:如果存在一个长度为20, 值为1-20的顺序一维数组,需要查找到1所在的索引。二分查找基本需要查找4次才能查找到;而通过插值查找索引在0位置的数据,只需要一次,即:

middle = 0 + (19 - 0) * (1 - 1) / (20 - 1) = 0;
arr[0] = 1;

2,插值查找代码实现

package com.self.datastructure.search;


/**
 * 插入查找
 *
 * @author PJ_ZHANG
 * @create 2020-03-13 15:37
 **/
public class InsertValueSearch {

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(insertValueSearch(array, 0, array.length - 1, 10));
    }

    /**
     * 插入查找获取到对应值索引
     * @param array 目标数组
     * @param left 左索引
     * @param right 右索引
     * @param target 目标值
     * @return
     */
    public static int insertValueSearch(int[] array, int left, int right, int target) {
        if (left > right) {
            return -1;
        }
        // 插入查找, 获取到自适应middle索引
        int middle = left + (right - left) * (target - array[left]) / (array[right] - array[left]);
        System.out.println("middle: " + middle);
        // 大于 向右查找
        if (target > array[middle]) {
            return insertValueSearch(array, middle + 1, right, target);
        } else if (target < array[middle]) { // 小于, 向左查找
            return insertValueSearch(array, left, middle - 1, target);
        } else {
            return middle;
        }
    }

}

3,注意事项
对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找,速度较快
关键字不均匀的情况下,该方法不一定比二分查找速度快

人已赞赏
Java

vue打包后运行报Uncaught SyntaxError: Unexpected token '<'?解决办法

2020-10-16 18:48:20

Java

版本控制工具有哪些?简述其工作流程

2020-10-19 14:55:10

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
'); })();