文档章节

查找--插值查找(Java)

o
 osc_kb5fqz4x
发布于 07/01 07:10
字数 345
阅读 27
收藏 0

精选30+云产品,助力企业轻松上云!>>>

查找--插值查找(Java)

博客说明

文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢!

介绍

插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。

自适应

计算自适应mid

int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])

代码

package cn.guizimo.search;

public class InsertValueSearch {
    public static void main(String[] args) {
        int max = 100;
        int[] arr = new int[max];
        for (int i = 0; i < max; i++) {
            arr[i] = i + 1;
        }
        int index = insertValueSearch(arr, 0, arr.length - 1, 100);
        if(index == -1){
            System.out.println("未找到");
        }else {
            System.out.println("下标为:"+index);
        }
    }

    public static int insertValueSearch(int[] arr, int left, int right, int value) {
        if (left > right || value < arr[0] || value > arr[arr.length - 1]) {
            return -1;
        }
        int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
        int midValue = arr[left];
        if (value > arr[mid]) {
            return insertValueSearch(arr, mid + 1, right, value);
        } else if (value < arr[mid]) {
            return insertValueSearch(arr, left, mid - 1, value);
        } else {
            return mid;
        }
    }
}

注意的事项

  • 对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找, 速度较快.
  • 关键字分布不均匀的情况下,该方法不一定比折半查找要好

感谢

尚硅谷

万能的网络

以及勤劳的自己

关注公众号: 归子莫,获取更多的资料,还有更长的学习计划

o
粉丝 0
博文 61
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
【Java】 大话数据结构(10) 查找算法(1)(顺序、二分、插值、斐波那契查找)

本文根据《大话数据结构》一书,实现了Java版的顺序查找、折半查找、插值查找、斐波那契查找。 注:为与书一致,记录均从下标为1开始。 顺序表查找 顺序查找 顺序查找(Sequential Search):从...

osc_ntgi5nw2
2018/06/27
5
0
查找--插值查找(Java)

查找--插值查找(Java) 博客说明 文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢! 介绍 插值查找算法类似于二分查找,不同...

归子莫
06/30
6
0
查找--插值查找(Java)

查找--插值查找(Java) 博客说明 文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢! 介绍 插值查找算法类似于二分查找,不同...

归子莫
06/30
0
0
查找算法总结及其算法实现Python/Java

本文分享自微信公众号 - 后端技术漫谈(Rude3Knife)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。...

后端技术漫谈
2019/04/19
0
0
查找算法总结及其算法实现Python/Java

本文分享自微信公众号 - 后端技术漫谈(Rude3Knife)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。...

后端技术漫谈
2019/03/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Kafka如何在千万级别时优化JVM GC问题?

大家都知道Kafka是一个高吞吐的消息队列,是大数据场景首选的消息队列,这种场景就意味着发送单位时间消息的量会特别的大,那既然如此巨大的数据量,kafka是如何支撑起如此庞大的数据量的分发...

hummerstudio
06/18
6
0
我打赌!90%程序员都破解不了这个粽子,不信你试!

放假了 各位读者朋友们,马上就是端午小长假啦,开心激动有木有? 新的故事文章还在创作中,写了初稿感觉不太满意又推倒重来。其实写故事还是挺难的,读者可能第一次第二次有新鲜感,写多了就...

轩辕之风
06/24
30
0
如何删库跑路?教你使用Binlog日志恢复误删的MySQL数据

前言 “删库跑路”是程序员经常谈起的话题,今天,我就要教大家如何删!库!跑!路! 开个玩笑,今天文章的主题是如何使用Mysql内置的Binlog日志对误删的数据进行恢复,读完本文,你能够了解...

后端技术漫谈
01/14
28
0
PHP设计模式之代理模式

PHP设计模式之代理模式 代理人这个职业在中国有另外一个称呼,房产经济人、保险经济人,其实这个职业在国外都是叫做房产代理或者保险代理。顾名思义,就是由他们来帮我们处理这些对我们大部分...

硬核项目经理
2019/09/23
11
0
Redis的复制模式

Redis的复制功能分为同步(sync)和命令传播(command propagate)两个操作。 同步 同步操作用于将从服务器的数据库状态更新至主服务器当前所处的数据库状态。 1. 旧版本的执行步骤 从服务器...

osc_s9cni3go
42分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部