龙空技术网

java实现插值查找

一个IT男的笔记 86

前言:

如今你们对“java 字符串插值”大概比较注意,看官们都需要分析一些“java 字符串插值”的相关知识。那么小编在网上搜集了一些关于“java 字符串插值””的相关文章,希望各位老铁们能喜欢,大家快快来学习一下吧!

简介

插值查找,有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找,将查找点的选择改进为自适应选择,提高查找效率。

图片说明

原理

举例说明

代码实现

package com.zyp.query;/** * 插值排序 * @author zyp * @create 2022/2/22 */public class InsertSearch {    public static void main(String[] args){        //待查找数组        int[] array = new int[]{1,2,3,4,5,6,7,8,9,10};        int index = insertQuery(array, 0, array.length - 1, 7);        System.out.println("找到的下标为:"+index);    }    /**     *     * @param array 待查找数组     * @param left 开始查找数据下标     * @param right 结束查找数据下标     * @param data 查找数据     * @return 找到元素所在数组的下标     */    public static int insertQuery(int[] array,int left,int right,int data){        //必须要有,否则可能出现下标越界        if(left > right || data < array[0] || data > array[array.length-1]){            return -1;        }        /**         * mid值的公式是怎么来的呢         * 之前二分法我们的mid = (left+right)/2 => left + 1/2(rihjt-left)         * 这里只是把1/2用(data - array[left])/(array[right]-array[left])替换         */        int mid = left + (right - left) * (data - array[left]) / (array[right]-array[left]);        int midValue = array[mid];        if(data > midValue){            return insertQuery(array, mid + 1, right, data);        }else if(data < midValue){            return insertQuery(array, left, mid - 1, data);        }else{            return mid;        }    }}
总结

插值查找类似与二分查找。对于数据量大的以及关键字分布均匀的有序序列来说,插值查找的速度较快。对于分布不均匀的有序序列来说,该算法不一定比二分查找要好

标签: #java 字符串插值 #java字符串插值 #插值查找算法流程图