【查找算法】插值查找

news/2024/4/15 5:17:53/文章来源:https://blog.csdn.net/suiyishiguang/article/details/136472246

文章目录

  • 一:插值查找
    • **代码公式:int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);**
    • 1.1 基本概念
    • 1.2 基本思想
    • 1.3 原理介绍
  • 二:代码实现

一:插值查找

代码公式:int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);

1.1 基本概念

插值查找,有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找,将查找点的选择改进为自适应选择,提高查找效率。插值查找是在二分查找的基础上进行的改进,二分查找每次将查找的范围缩小一半,即mid=(low+high) / 2可以看出,折半查找是一种机械式的查找方式,不是自适应的。因此, 在数值分布相对均匀的查找表中, 我们将计算mid的方式改为自适应的查找,即mid=low+(key-a[low])/(a[high]-a[low])*(high-low)能够有效提高查找的效率

1.2 基本思想

  1. 插值查找类似平时我们查字典的时候,查一个以 s 开头的单词时,绝对不会用二分查找,从字典的中间第一页开始,因为我们知道它的大概位置是在字典的较后面部分,所以可以从后面的某处查起。我们先从首字母 s 的地方开始查找,然后再根据第二个字母在字母表中的位置,找到对应位置再继续查找,这样重复这个过程,直到找到我们查找的这个单词这就是插值查找的基本思想
  2. 插值查找除了要求查找的数据是顺序存储的有序数据外,还要求根据元素的关键字在数据中均匀分布,这样就可以按照比例插值

1.3 原理介绍

  1. 插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。
  2. 将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right,key 就是前面我们讲的 findValue

在这里插入图片描述

二:代码实现

package com.sysg.dataStructuresAndAlgorithms.find;/*** 插值查找*/
public class InsertValueSearch {public static void main(String[] args) {int[] array = new int[100];for (int i = 0; i < 100; i++) {array[i] = i + 1;}int index = insertValueSearch(array, 0, array.length - 1, 5);System.out.println(index);}/*** 插值查找算法** @param array     原始数组* @param left      左节点* @param right     右节点* @param findValue 需要查找的值* @return 如果找到,就返回查找值得下标。如果找不到就返回-1*/public static int insertValueSearch(int[] array, int left, int right, int findValue) {if (left > right || findValue < array[0] || findValue > array[array.length - 1]) {return -1;}//求出middle,自适应的值int middle = left + (right - left) * (findValue - array[left]) / (array[right] - array[left]);//获取中间值int middleValue = array[middle];if (findValue > middleValue) {//如果需要查找的值大于中间值,则向右递归return insertValueSearch(array, middle + 1, right, findValue);} else if (findValue < middleValue) {//如果需要查找的值小于中间值,则向左递归return insertValueSearch(array, left, middle - 1, findValue);} else {return middle;}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_998734.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python笔记|基础算数运算+数字类型(1)

重新整理记录一下python的基础知识 基础运算符 、-、*、/ &#xff1b;括号 ()用来分组。 >>>2 2 4 >>>50 - 5*6 20 >>>(50 - 5*6) / 4 5.0 >>>8 / 5 1.6向下取整除法&#xff1a;向下舍入到最接近的整数的数学除法。运算符是 //。比如1…

Win UI3开发笔记(四)设置主题续2

本机深色主题下设置的背景颜色可以作用于整个对话框&#xff0c;本机浅色模式下设置的背景颜色只作用与下边的部分。 如果本机选深色&#xff0c;程序选浅色&#xff0c;设置为light只对上部分管用&#xff0c;下部分不管用。如图&#xff0c;左边那个hello按钮要看不见了。。…

C++指针(四)万字图文详解!

个人主页&#xff1a;PingdiGuo_guo 收录专栏&#xff1a;C干货专栏 前言 相关文章&#xff1a;C指针&#xff08;一&#xff09;、C指针&#xff08;二&#xff09;、C指针&#xff08;三&#xff09; 本篇博客是介绍函数指针、函数指针数组、回调函数、指针函数的。 点赞破六…

怎么将pom在文件放到src下方

今天在IDEA从git拉取项目的时候&#xff0c;发现pom.xml文件在文件夹src的上方&#xff0c;平时看惯了项目的pom.xml文件在文件夹src的下方&#xff0c;应该怎么去设置呢&#xff1f; 点击设置——>点击Folder Always on Top 即可 参考&#xff1a;http://t.csdnimg.cn/s34…

2024蓝桥杯每日一题(二分)

一、第一题&#xff1a;教室 解题思路&#xff1a;二分差分 对天数进行二分&#xff0c;在ck函数中用差分方法优化多次区间累加。 【Python程序代码】 n,m map(int,input().split()) a [0] list(map(int,input().split())) d,s,t [0]*(m5),[0]*(m5),[0]*(m5) for…

CSS补充(下),弹性布局(上)

高级选择器 1.兄弟选择器 2.同时满足 div.bg{background-color: red;}p.bg{background-color: green;}spam.bg{background-color: blue;}注&#xff1a;选择器中间没有空格&#xff0c;有明确标识的选择器写在后面 3.各种伪类的应用 3.1作为第几个子元素 选择器:nth-child…

LeetCode 2917.找出数组中的 K-or 值:基础位运算

【LetMeFly】2917.找出数组中的 K-or 值&#xff1a;基础位运算 力扣题目链接&#xff1a;https://leetcode.cn/problems/find-the-k-or-of-an-array/ 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 nums 中的 K-or 是一个满足以下条件的非负整数&#xff1a; 只有…

SPSS直接输出三线表

STEP1 下载三线表.stt至安装目录的Looks文件夹 STEP2 在SPSS菜单栏中找到 编辑-选项-透视表 表外观下拉到最底&#xff0c;选择三线表&#xff08;如果第一步没保存对是不会出现的&#xff09;&#xff0c;然后点击确定 效果&#xff1a;

k8s 网络概念与策略控制

一、Kubernetes 基本网络模型 Kubernetes 的容器网络模型可以把它归结为约法三章和四大目标。 1、约法三章 约法三章确保了Kubernetes容器网络模型的基本特性&#xff1a; ① 任意两个 pod 之间可以直接通信&#xff1a;在Kubernetes中&#xff0c;每个 Pod 都被分配了一个…

【比较mybatis、lazy、sqltoy、mybatis-flex、easy-query操作数据】操作批量新增、分页查询(三)

orm框架使用性能比较 比较mybatis、lazy、sqltoy、mybatis-flex、easy-query操作数据 环境&#xff1a; idea jdk17 spring boot 3.0.7 mysql 8.0测试条件常规对象 orm 框架是否支持xml是否支持 Lambda对比版本mybatis☑️☑️3.5.4sqltoy☑️☑️5.2.98lazy✖️☑️1.2.4…

cocos creator 3.7.2使用shader实现图片扫光特效

简介 功能&#xff1a;图片实现扫光效果 引擎&#xff1a;cocos Creator 3.7.2 开发语言&#xff1a;ts 完整版链接 链接https://lengmo714.top/284d90f4.html 效果图 shader代码 // Copyright (c) 2017-2020 Xiamen Yaji Software Co., Ltd. CCEffect %{techniques:- pas…

探索数据结构:单链表的实战指南

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属专栏&#xff1a;数据结构与算法 贝蒂的主页&#xff1a;Betty‘s blog 前言 在上一章节中我们讲解了数据结构中的顺序表&#xff0c;知道了顺序…

腾讯云服务器运行yum检测超级慢问题

公司使用腾讯云服务器。最近买的几台服务器使用yum命令安装或 更新软件特别慢。如下图&#xff1a; 从图中看出网络速度极慢。 大约要等5-10分钟检测和更新配置完毕&#xff0c;进入到软件下载界面下载软件速度就快了。 琢磨了一下&#xff0c;连接慢并不是连接不上。查看yum…

【工具】Raycast – Mac提效工具

引入 以前看到同事们锁屏的时候&#xff0c;不知按了什么键&#xff0c;直接调出这个框&#xff0c;然后输入lock屏幕就锁了。 跟我习惯的按Mac开机键不大一样。个人觉得还是蛮炫酷的&#xff5e; 调研 但是由于之前比较繁忙&#xff0c;这件事其实都忘的差不多了&#xff0…

便捷在线导入:完整Axure元件库集合,让你的设计更高效!

Axure元件库包含基本的工具组件&#xff0c;可以使原型绘制节省大量的重复工作&#xff0c;保持整个设计页面的一致性和标准化&#xff0c;同时显得专业。Axure元件库就像我们日常生活中的门把手、自行车踏板和桌子上的螺丝钉&#xff0c;需要组装才能使用。作为一名成熟的产品…

Jmeter接口测试之常用断言

在接口测试中&#xff0c;我们需要检查请求处理结果是否正确。当请求的响应状态码为200&#xff0c;是否表时接口功能正常呢&#xff1f;显然是不正确的。 响应状态为200&#xff0c;只能表明服务处理了你的请求&#xff0c;同时进行了结果返回&#xff1b;但并不能代表处理的…

Redis常用指令,jedis与持久化

1.redis常用指令 第一个是key的常用指令&#xff0c;第二个是数据库的常用指令 前面的那些指令都是针对某一个数据类型操作的&#xff0c;现在的都是对所有的操作的 1.key常用指令 key应该设计哪些操作 key是一个字符串&#xff0c;通过key获取redis中保存的数据 对于key…

数字人ai直播软件突破AI大模型技术,改变未来科技格局!

数字人AI直播软件在AI大模型技术上的突破&#xff0c;将不可避免地改变未来科技格局。这一突破让人们看到了AI技术的无限可能性&#xff0c;并为未来的科技发展打开了新的大门。 AI大模型技术是近年来人工智能领域的一个热点&#xff0c;它通过构建庞大、复杂的神经网络模型&a…

99.qt qml-单例程序实现

在之前讲过: 58.qt quick-qml系统托盘实现https://nuoqian.blog.csdn.net/article/details/121855993 由于,该示例只是简单讲解了系统托盘实现,并没有实现单例程序,所以多次打开后就会出现多个exe出现的可能,本章出一章QML单例程序实现, 多次打开始终只显示出第一个打开…

Docker-完整项目的部署(保姆级教学)

目录 1 手动部署(白雪版) 1.1 创建网络 1.2 MySQL的部署 1.2.1 准备 1.2.2 部署 1.3 Java项目的部署 1.3.1 准备 1.3.1.1 将Java项目打成jar包 1.3.1.2 编写Dockerfile文件 1.3.2 部署 1.3.2.1 将jar包、Dockerfile文件放在linux同一个文件夹下 1.3.2.2 构建镜像 …