查找算法之插值查找

梦里梦外; 2023-07-10 08:25 94阅读 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 条评论，94人围观）

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

相关阅读

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

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

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

相关 java插值查找算法

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

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

相关查找算法之插值查找

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

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

相关查找算法——插值查找（Java实现）

当我们的数组是一个从1到100的有序数组的时候，况且这个时候需要查找的是1，使用二分查找的话，很显然是比较麻烦的。这个时候就要使用到插值查找。插值查找算法类似于二分查找，

冷不防/ 2023年03月13日 13:01/ 0 赞/ 31 阅读

相关数据查找算法：插值查找

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

迷南。/ 2023年02月28日 01:22/ 0 赞/ 82 阅读

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

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

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

相关查找-插值查找

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

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

相关插值查找算法

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

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

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

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

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

相关插值查找算法实战

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

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