搜索算法系列之三(插值查找)
前言
插值查找仅适用于有序数据、有序数组,和二分查找类似,更讲究数据有序均匀分布。
算法原理
插值查找(interpolation search)是一种查找算法,它与二分查找类似,但在寻找元素时更加智能化。这种算法假设数据集是等距的或者有序的,然后根据要查找的值在数据集中的位置进行估计,而不是简单地将查找范围划分为两半。
插值查找的步骤如下:
-
确定查找范围:首先确定要查找的元素在哪个范围内。通常情况下,这是通过比较要查找的值和数据集的第一个和最后一个元素来确定的。
-
计算估计位置:通过插值公式计算要查找的值在当前查找范围内的估计位置。插值公式通常是
(value - array[low]) / (array[high] - array[low]) * (high - low) + low,其中low和high分别是当前查找范围的起始和结束位置。 -
检查估计位置:将估计位置与要查找的值进行比较。
- 如果估计位置上的值等于要查找的值,则找到了目标元素。
- 如果估计位置上的值大于要查找的值,则在估计位置的左侧继续进行插值查找。
- 如果估计位置上的值小于要查找的值,则在估计位置的右侧继续进行插值查找。
-
重复直到找到目标元素或者确定元素不存在。
插值查找适用于数据集分布比较均匀的情况下,因为它是根据数据集的分布情况进行估计的。在数据集分布不均匀的情况下,插值查找可能会失效,效率不如二分查找。
上述公式说明:
value为查找的值。low、high为数据集首尾下标。array[low]、array[high]为数据集首尾值。
(value-array[low])/(array[high]-array[low])计算查找值在有序队列所处位置的比值。
代码实现(c)
#include <stdio.h>// 插值查找函数
int interpolationSearch(int arr[], int low, int high, int key) {if (low <= high) {// 计算插值的索引int mid = low + (high - low) * (double)((key - arr[low]) / (arr[high] - arr[low]));// 如果元素等于key,返回midif (arr[mid] == key)return mid;// 如果元素小于key,在右侧递归查找if (arr[mid] > key)return interpolationSearch(arr, low, mid - 1, key);// 如果元素大于key,在左侧递归查找return interpolationSearch(arr, mid + 1, high, key);}// 如果数组不存在key,返回-1return -1;
}int main() {int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};int n = sizeof(arr) / sizeof(arr[0]);int key = 7;// 查找元素int index = interpolationSearch(arr, 0, n - 1, key);// 输出结果if (index != -1)printf("元素在数组中的索引为: %d\n", index);elseprintf("元素不在数组中。\n");return 0;
}
注意计算比例时转double类型,否则会失效。
优点与局限性
优点:
- 适用于均匀分布的数据集: 插值查找在数据集均匀分布时效果更为显著,能够更准确地估计目标值的位置。
- 相对于二分查找的改进: 在某些情况下,插值查找的效率较二分查找更高,尤其是对于近似均匀分布的数据。
局限:
- 对于不均匀分布的数据效果不佳: 当数据分布不均匀时,插值查找的性能可能较差,甚至不如二分查找。
- 可能导致溢出: 在计算插值位置时,由于分母可能为零,导致除法溢出的风险。
复杂度
插值查找的时间复杂度取决于数据集的分布情况。在理想情况下(即数据集均匀分布),插值查找的时间复杂度可以达到 O(log log n)。这是因为它根据数据集的分布情况进行估计,可以更快地缩小查找范围。
然而,在最坏情况下,插值查找的时间复杂度可以达到 O(n),这通常发生在数据集中存在大量重复元素或者数据集分布不均匀的情况下。在这种情况下,插值查找可能会退化为线性搜索,效率明显下降。
总体来说,插值查找在数据集分布均匀的情况下具有更好的性能,但在数据集分布不均匀或存在大量重复元素时,效率可能不如二分查找等其他查找算法。因此,在实际应用中,需要根据具体情况选择合适的查找算法。
相关文章:
搜索算法系列之三(插值查找)
前言 插值查找仅适用于有序数据、有序数组,和二分查找类似,更讲究数据有序均匀分布。 算法原理 插值查找(interpolation search)是一种查找算法,它与二分查找类似,但在寻找元素时更加智能化。这种算法假设数据集是等距的或者有…...
前端奇怪面试题总结
面试题总结 不修改下面的代码进行正常解构 这道题考的是迭代器和生成器的概念 let [a,b] {a:1,b:2}答案 对象缺少迭代器,需要手动加上 Object.prototype[Symbol.iterator] function* (){// return Object.values(this)[Symbol.iterator]()return yeild* Object.v…...
NPM--最新淘宝镜像源地址
最新淘宝镜像源地址: 原来的 https://registry.npm.taobao.org 已替换为 https://registry.npmmirror.com 查看镜像源 npm config get registry 更换为淘宝最新镜像源 npm config set registry https://registry.npmmirror.com...
vue3中实现地区下拉选择组件封装
1组件文件 新建一个文件夹内,包含inde.vue,index.ts,pac.json这三个文件 index.vue文件 <template><el-cascaderv-model"data":options"pcaData":style"{ width: props.width }":placeholder"props.placeholder&quo…...
责任链模式案例
需求背景: 请你设计一个员工休假审批流程,当员工的休假天数<1时,由直接领导审批,休假天数<2时,分别由直接领导、一级部门领导审批,休假天数>3时,分别由直接领导、一级部门领导、分管领…...
Android NDK开发(二)——JNIEnv、jobject与jclass关系
本文主要讲解Android NDK开发中JNIEnv、jobject与jclass的相关知识,并用c和c两种语言实现了jobject和jclass。 本专栏知识点是通过<零声教育>的音视频流媒体高级开发课程进行系统学习,梳理总结后写下文章,对音视频相关内容感兴趣的读者…...
机器学习入门:sklearn基础教程
Scikit-learn(简称sklearn)是Python中最受欢迎的机器学习库之一,它提供了丰富的机器学习算法和工具,适用于各种任务和场景。本文将为您介绍sklearn的基础知识和常用功能,带您踏入机器学习的世界。 1. 安装与导入 首先…...
26 | 备库为什么会延迟好几个小时?
在官方的 5.6 版本之前,MySQL 只支持单线程复制,由此在主库并发高、TPS 高时就会出现严重的主备延迟问题。 coordinator 就是原来的 sql_thread, 不过现在它不再直接更新数据了,只负责读取中转日志和分发事务。真正更新日志的,变成了 worker 线程。而 work 线程的个数,就是…...
linux 如何解压.tar 文件
要在 Linux 中解压 tar 文件,请使用以下命令: tar -xvf yourfile.tar 1 其中,“yourfile.tar”是您要解压的文件名。 这个命令会将文件解压到当前目录中。如果想要将文件解压到不同的目录中,可以使用 -C 选项指定路径。例如&…...
盘点企业信息防泄密软件对比|揭秘企业信息防泄密软件好用榜
在当今信息化社会,企业信息防泄密软件的需求日益凸显。这些软件不仅关乎企业的核心竞争力,更直接关系到企业的生死存亡。本文将对市面上几款主流的企业信息防泄密软件进行深入对比分析,以期为企业提供有益的参考。 一、企业信息防泄密软件好…...
html--瀑布效果
<!doctype html> <html> <head> <meta charset"utf-8"> <title>瀑布效果</title><style> body {background: #222;color: white;overflow:hidden; }#container {box-shadow: inset 0 1px 0 #444, 0 -1px 0 #000;height: 1…...
vue视图不刷新强制更新数据this.$forceUpdate()
在vue中,更新视图数据,不刷新页面,需要强制更新数据才可以 前言 在对数据就行添加和删除时,发现页面视图不更新,排除发现需要强制更新才可以 点击添加或删除,新增数据和删除就行,但在不使用fo…...
2024年电工杯数学建模竞赛A题B题思路代码分享
您的点赞收藏是我继续更新的最大动力! 一定要点击如下的卡片链接,那是获取资料的入口! 点击链接加入群聊【2024电工杯】:http://qm.qq.com/cgi-bin/qm/qr?_wv1027&kUMFX8lu4qAm0XkZQ6JkW5m5O9F_mxf-L&authKey0hWdf7%2F…...
leetcode 797.所有可能的路径
思路:dfs。 其实很简单,我们只需要和昨天做的题一样,直接遍历所给数组中的元素,因为这里的数组意义已经很清楚了,就是当前位置的结点和哪一个顶点有联系。 注意:在存储路径的时候,我们需要按顺…...
NPM 基础
介绍 npm 是 JavaScript 编程语言的一个包管理器,它允许开发者安装、共享和管理依赖项。npm 与 Node.js 紧密集成,是 Node.js 生态系统中不可或缺的一部分。它提供了一个命令行工具,使得开发者能够轻松地安装、配置和管理项目所需的各种包。…...
WPF之创建无外观控件
1,定义无外观控件。 定义默认样式,在其静态构造函数中调用DefaultStyleKeyProperty.OverrideMetadata()。 //设置默认样式DefaultStyleKeyProperty.OverrideMetadata(typeof(ColorPicker), new FrameworkPropertyMetadata(typeof(ColorPicker))); 在项目…...
MySQL利用变量进行查询操作
新建连接,自带world数据库,里面自带city表格。 # MySQL利用变量进行查询操作 set cityNameHaarlemmermeer; select * from city where NamecityName;# 多个结果查询 set cityName1Haarlemmermeer; set cityName2Breda; set cityName3Willemstad; selec…...
算法--动态规划
动态规划(Dynamic Programming, DP)是一种算法设计技巧,用于解决具有重叠子问题和最优子结构性质的问题。通过将原问题分解为相对简单的子问题的方式来求解复杂问题,动态规划避免了计算重复子问题,从而提高了算法的效率…...
Python基础详解一
一,print打印 print("hello word") print(hello word) 双引号和单引号都可以 二,数据类型 Python中常用的有6种值的类型 输出类型信息 print(type(11)) print(type("22")) print(type(22.2)) <class int> <class str&…...
3.SpringSecurity基本原理
SpringSecurity本质是一个过滤器链。十多个过滤器构成一个过滤器链。 这些过滤器在项目启动就会进行加载。每个过滤器执行放行操作才会执行下一个过滤器。 常见过滤器 FilterSecurityInterceptor 是一个方法级的权限过滤器,基本位于过滤器链的最底部。 Excepti…...
如何通过Superalgos教育模块快速掌握算法交易:新手入门完整指南
如何通过Superalgos教育模块快速掌握算法交易:新手入门完整指南 【免费下载链接】Superalgos Superalgos/Superalgos: 是一个开源的分布式社交网络分析和数据挖掘平台。适合对大数据分析、机器学习、区块链以及分布式系统有兴趣的开发者。 项目地址: https://gitc…...
某高校学生考微软MOS认证加学分
临近毕业季,到底是谁的学分还没有修够?微软MOS认证证书也可以加学分,每天学习两个小时,一周就可以完成考试,当天就出证书!📌关于难度选择版本难度:2016 < 2019 < 365ÿ…...
Oracle数据库架构入门概述
本文分为四个部分简单概述 一、入门概述 二、数据库实例简述 三、数据库物理存储和逻辑存储结构简述 四、网络体系结构概述 入门概述 Oracle 数据库服务器包括一个数据库和至少一个数据库实例 (通常是指只有一个实例)。 因为实例和数据库关联紧密&#x…...
Antares LoRaWAN库深度解析:嵌入式LoRaWAN MAC层实现指南
1. Antares LoRaWAN 库深度技术解析:面向嵌入式工程师的 LoRaWAN MAC 层实现指南 1.1 库定位与工程价值 Antares LoRaWAN 是一个专为 Arduino 生态设计的轻量级 LoRaWAN MAC 层实现库,其核心价值不在于功能堆砌,而在于 可理解性、可调试性与…...
MoveIt Config 配置文件完整一致性检查
检查范围(全部核对完毕)ros2_control xacro(硬件接口 / 关节)initial_positions.yaml(初始位置)srdf(运动组 / 关节)joint_limits.yaml(关节限制)kinematics.…...
WWW-万维网
万维网的概念与组成结构万维网(World Wide Web,WWW)是一个分布式的信息存储空间,在这个空间中:一个事物被称为一样 “资源”,并由一个全域 “统一资源定位符”(URL)标识。这些资源通…...
YOLOv8目标检测新玩法:用VMamba替换C2f模块,我在DDSM医疗数据集上mAP涨到了0.724
YOLOv8与VMamba融合:医疗影像目标检测的突破实践 在医疗影像分析领域,目标检测技术正经历着从传统卷积神经网络到新型架构的转变。最近,我们将YOLOv8模型中的C2f模块替换为VMamba模块,在DDSM乳腺X光数据集上取得了mAP 0.724的显著…...
从‘各玩各的’到‘协同作战’:聊聊多传感器SLAM中坐标系对齐的那些‘坑’与最佳实践
从‘各玩各的’到‘协同作战’:多传感器SLAM坐标系对齐的工程实践指南 当激光雷达的轨迹点云与相机的视觉路径在三维空间中"貌合神离",工程师们往往面临一个关键抉择:是强行统一时间基准,还是重新建立空间映射关系&…...
根据您提供的写作范围,我为您总结的标题为:“昆通泰MCGS7.7嵌入版:6车位停车场监控系统仿...
6车位停车场监控系统昆通泰MCGS7.7嵌入版仿真运行带运行效果视频6车位停车场监控系统用昆通泰MCGS7.7嵌入版做仿真,真的是新手友好型项目——不用扛硬件、不用接复杂通讯,靠内部变量和几段脚本就能把核心逻辑跑通,还能直观看到实时效果&#…...
别再死记硬背了!用Python脚本+Modbus Poll工具,5分钟搞懂Modbus功能码怎么用
用PythonModbus Poll实战:5分钟解锁功能码核心逻辑 第一次接触Modbus协议时,那些晦涩的功能码总让我头疼——01H、03H、05H这些十六进制代码就像天书,文档里的理论描述看完就忘。直到我发现用Python脚本配合Modbus Poll工具进行实操测试&…...
