查找算法之插值查找

梦里梦外; 2023-07-10 08:25 11阅读 0赞

package com.yg.search;/*
    @author  Mu_Mu
    @date    2020/3/1  10:08
    */
    
    public class InsertValueSearch {
        
        public static void main(String[] args) {
        
            int arr[] = new int[100];
            for (int i = 0; i < 100; i++) {
        
                arr[i] = i + 2;
            }
            int index = insertValueSearch(arr, 0, arr.length - 1,3 );
            System.out.println("index:" + index);
        }
    
        //插值排序需要有序序列，原理是斜率，对于每个元素间隔相同的序列一次就可以找到
        //找第一个元素和最后一个元素也可以直接找到
        private 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]);
    
            //小于arr【mid】说明findVal在mid的左边
            if (findVal < arr[mid]) {
        
                return insertValueSearch(arr, left, mid - 1, findVal);
            } else if (findVal > arr[mid]) {
          //大于arr【mid】说明findVal在mid的右边边
                return insertValueSearch(arr, mid + 1, right, findVal);
            } else {
        
                return mid;
            }
    
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法系列 | 11】深入解析查找算法之—插值查找

查找算法是计算机科学中的一类算法，用于在数据集中寻找特定值或数据项。其目标是确定数据是否存在于给定的数据结构中，并找到数据项的位置（索引）或其他相关信息。不同的查找算法适...

喜欢ヅ旅行/ 2024年04月28日 08:09/ 0 赞/ 66 阅读

相关 java插值查找算法

1. 插值查找原理介绍: 插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。 1. 将折半查找中的求 mid 索引的公式 , low 表示左

ゞ浴缸里的玫瑰/ 2024年03月27日 13:24/ 0 赞/ 89 阅读

相关 Java 与查找算法（4）：插值查找

一、插值查找插值查找是一种基于二分查找算法的优化算法，用于在有序数组中查找目标元素。与二分查找每次取中间位置的元素进行比较不同，插值查找根据目标元素与数组中最小值和最大

深藏阁楼爱情的钟/ 2024年03月16日 10:06/ 0 赞/ 57 阅读

相关算法_查找算法(线性查找、二分查找、插值查找、斐波那契查找)

文章目录线性查找二分查找插值查找斐波那契查找线性查找 / 线性查找所有结果

比眉伴天荒/ 2023年07月11日 05:53/ 0 赞/ 3 阅读

相关查找算法之插值查找

package com.yg.search;/ @author Mu_Mu @date 2020/3/1 10:08 /

梦里梦外;/ 2023年07月10日 08:25/ 0 赞/ 12 阅读

相关查找算法之插值查找（深入理解，详细说明）

回顾一下之前讲述的二分查找。其基本的思路就是找到中间值mid将序列分成两个部分，然后判断要查找的值是在左子序列还是右子序列进而继续找到中间值再分裂。可以看到，每次分裂是将原序列

不念不忘少年蓝@/ 2023年02月18日 12:57/ 0 赞/ 49 阅读

相关查找-插值查找

1.插值查找前言现在我们的新问题是，为什么一定要折半，而不是折四分之一或者折更多呢？例如，在英文词典里查”apple”,你下意识里翻开词典是翻前面的书页还是后面的书

小咪咪/ 2022年09月30日 12:57/ 0 赞/ 203 阅读

相关插值查找算法

插值查找算法是基于二分查找算法的,只是在查找的过程中计算Middle的方式有所改变,比如一组可以通过二分查找算法计算出的nMid索引的值,是这样子计算的 nMid=(nLow

淡淡的烟草味﹌/ 2022年08月07日 11:58/ 0 赞/ 174 阅读

相关查找算法：插值查找算法实现及分析

插值查找算法介绍插值查找（Interpolation Search）是根据要查找关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式k

川长思鸟来/ 2022年05月29日 22:52/ 0 赞/ 276 阅读

相关插值查找算法实战

一插值查找原理插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。二插值查找公式将二分查找中的求 mid 索引的公式进行改造

港控/mmm°/ 2021年07月24日 16:51/ 0 赞/ 433 阅读