首页 > 知识库 > 正文

插值查找是什么 关于插值查找的详细介绍

插值查找,有序表的一种查找方式。插值查找是根据查找关键子与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找,将查找点的选择改进为自适应选择,提高查找效率。

基本思想

查找( Search)是指从一批记录中找出满足指定条件的某一记录的过程,查找又称为检索。查找算法广泛应用于各类应用程序中。因此,一个有效的查找算法往往可以大大提高程序的执行效率。在实际应用中,数据的类型千变万化,每条数据项往往包含多个数据域。但是,在执行查找操作时,往往只是指定一个或几个域的值,这些作为查找条件的域称为关键字(Key),关键字分为两类。

我们遇到的大部分查找问题都是以主关键字为准的。而且为了方便读者的理解,后面将以整型数据关键字为例进行讲解,其他类型的关键字的查找算法与此类似。如果查找到相应的数据项,往往需要返回该数据项的地址或者位置信息。这样程序中即可通过位置信息来进行显示数据项、插入数据项、删除数据项等操作。如果没有查找到相应的数据项,则可以返回相应的提示信息。

在实际应用中,针对不同的情况往往可以选择不同的查找算法。对于无顺序的数据,只有逐个比较数据,才能找到需要的内容,这种方法称为顺序查找。对于有顺序的数据,也可以采用顺序查找法逐个比较,但也可以采取其他更快速的方法找到所需数据。另外,对于一些特殊的数据结构,例如链表、树结构和图结构等,也都有相对应的合适的查找算法。 [1]

插值类似于平常查英文字典的方法,在查一个以字母C开头的英文单词时,决不会用二分查找,从字典的中间一页开始,因为知道它的大概位置是在字典的较前面的部分,因此可以从前面的某处查起,这就是插值查找的基本思想。

插值查找除要求查找表是顺序存储的有序表外,还要求数据元素的关键字在查找表中均匀分布,这样,就可以按比例插值。 [2]

性能分析

插值查找性能分析:算法在最好和最坏情况下的关键字比较次数是明显的,但平均情况的分析比较复杂,并且这里的“平均”与前面讨论过的查找算法的平均不同,这里是在元素满足某种分布情况下的平均。 [3]

适用条件

适合于关键字值分布均匀的集合。

应用

根据关键字的分布估计被查元素的位置,能更精确定位到被查找元素的位置,但应用有限。 [4]

其他查找算法

分块查找

若查找表中的数据元素的关键字是按块有序的,则可以做分块查找。分块查找又称索引顺序查找,是对顺序查找的一种改进。分块查找将查找表按块分成若干个子表,对每个子表建立一个索引项,再将这些索引项顺序存储,形成一个索引表。每个索引项包括两个字段:关键码字段(存放对应子表中的最大关键码值)和指针字段(存放指向对应子表的指针),这样索引表则是按关键码有序的。查找时,分成两步进行:先根据给定值kx在索引表中查找,以确定所要查找的数据元素属于查找表中的哪一块,由于索引表按关键码有序,因此可用顺序查找或折半查找;然后,再进行块内查找,因为块内无序,只能进行顺序查找。 [2]

顺序查找

顺序查找比较简单,执行的操作是从数据序列中的第1个元素开始,从头到尾依次逐个查找,直到找到所需要的数据或搜索整个数据序列。顺序查找主要针对数量较少的、无规则的数据。对于包含n个数据的数据序列,使用顺序查找方法查找数据,最理想的情况是目标数据位于数组的第1个,这样比较1次就能找到目标数据;而最差的情况是需要比较完所有的n个数据才能找到目标数据或者确认没有该数据。平均来说,使用顺序查找方法比较次数为n次,效率是比较低的。 [1]

为您推荐可能与“插值查找”相关的内容:

多项式插值法

多项式插值法是一种搜索方法。指用插值多项式φ(t)的极小点逼近寻求函数f(t)的极小点的方法具体做法是:求φ′(t)=0的根,作为f(t)的极小点的近似...

二叉排序树查找

二叉排序树查找的插入和删除结点十分方便。

查找表

在计算机科学中,查找表是用简单的查询操作替换运行时计算的数组或者 associative array 这样的数据结构。

散列查找

在进行查找时,在记录的存储位置与它的关键字之间建立一个确定的对应关系h,以线性表中每个元素的关键字K为自变量,通过函数h(K)计算出该元素的存储位置,我...

AVL[AVL树-二叉查找树]

AVL在计算机科学中是最先发明的自平衡二叉查找树。

C语言算法速查手册

 2216.2.2 [算法53] 牛顿法 2236.2.3 [算法54] 插值法...法求非线性方程组的实根 2336.2.7 【实例31】 用插值法求非线性...7章 代数插值法 2547.1 拉格朗日插值法 2547.1.1 [算法...

Excel2010VBA编程与实践

读者根据需要快速地查找。对于渴望学习和掌握新知识的Excel用户来说...本书的解题思路与代码防错技术、代码优化之道。本书的案例涉及基础应用、查找...11章,涉及制表的每个方面。前10章分别为基础理论篇、查找引用篇、数据处理...

即用即查JSP函数与对象参考手册

 required属性:指定属性值是否必需 22   2.4.3 fragment属性...可由表达式设置 23   2.4.5 type属性:指定属性值的类型 24...:指定属性的值 33   3.3 jsp:getProperty 动作...

中文版Excel2013宝典(第8版)

看上去更有吸引力 201.10.6对值求和 211.10.7创建图表...文本条目 262.1.3公式 262.2在工作表中输入文本和值 272.3在工作表中输入日期和时间 282.3.1输入日期值 282.3.2输入...

声明:本网内容收集自互联网,旨在传播知识仅供参考,不代表本网赞同其观点,文字及图片版权归原网站所有。

更多精彩内容推荐:

11月份即将来临,在北京,大伙的外地车怎么弄?是开回家还是把车卖了?纠结啊?

未办理进京证在支路以上等级道路不能停放,小区内,停车场内没事。...

头条上什么时候才有收入?

首先在回答这个问题之前,我需要说明一下,做为一个在头条上有收入的人,我来回答这个问题,绝对不是在炫耀!因为,我还不够格!说句实话,我现在还只是一个普通的头条号玩家,我在悟空问答,还得坚持垂直领域的回答,我是影视领域的,现在来回答你这问题,就已经跑题了,但是我知道做自媒体的不容易,...

你觉得拼多多靠谱吗?你在拼多多买过东西吗,具体是怎样的?

提到拼多多,很多人觉得里面卖的东西不怎么样,认为拼多多就是个卖水货的平台。但是你敢保证别的,知名的购物平台里就卖的没有质量差的商品吗?我就在拼多多里淘过几次东西,感觉还可以,价格也便宜,我不是给拼多多打广告,只是实话实说,1,到拼多多里面购物的,基本上有很多人,都是经济上并不富裕...

天津市的塘沽怎么样?

天津市塘沽的港口,就是天津这座城市的名片。也是这个城市的地标。塘沽区无论是在天津还是在国内的港口建设中都是非常让人瞩目的。天津市的塘沽也让所有人知晓。塘沽位于天津市的东部什天津滨海新区的中心区,总面积达859平方公里,它东面是渤海,交通非常便利。塘沽区,在2009整合了其他三个区...

头条收入是靠打赏吗?

想要在头条上获利,首先要出品优质内容,不论打赏还是流量付费都是需要有内容的支撑。首先提到头条的收益,必须要了解头条收益模式及头条的推荐模式。头条的收益模式大致分为几种:流量分成流量分成是头条类内容收益的基础,头条系产品主要为图文、视频、问答几大类,创作者将通过创作优质内容,获得用...

什么人千万不要吃花生?

花生想必被大多数人所熟知,一提到花生,隔壁的叔叔大爷就会说,哎呀小爽呀,自己榨的花生油吃的好不好呀,经常有人这样问我? 你说我能不能吃花生油呀?说到一种食材,他们总会有聊不完的话题,问不完的问题,其实,花生可以作为坚果类的一种,只不过花生当中油脂含量特别高,是属于能量高的一种坚果...

龙配什么属相好?

以属相配,十二属相是从属十二地支固定不变的。子鼠,丑牛,寅虎,辰龙,已蛇,午马,未羊,申猴,酉鸡,戌狗,亥猪。所谓合配不合配是从地支的合冲刑害上说的。合配就是要地支相合,地支相冲,相刑,相害就是不合配。地支有六合三合。六合是:子丑合,寅亥合,卯戌合,辰酉合,已申合,午未合。三合是...

人的寿命与抽烟、喝酒有关系吗?

人的寿命长短,与出生的时间和姓名有关,与抽烟喝酒没关系。抽烟喝酒活七、八十岁的很多,姻酒不来的,活四、五十岁死的人也不少。有人生了病,医生就说不能抽烟了,病人果然就不抽了,再大的烟瘾想忌忌不了,只要医生一句话,霎那间烟瘾就没了。可惜的是烟忌了人死了。为什么说寿命与出生时间有关呢?...

娱乐圈的哪些事情你知道后会瑟瑟发冷?

韩国D王朱智勋都复出主演好几部电影了,胜利和张紫妍事件呢?09年黄荷娜就和弟弟yun du,09年朴有天还不认识黄荷娜啊,到底谁害了谁?黄荷娜15年在JF办公室自己说其父亲和JF高层有关系,有视频为证。好多粉丝都喜欢有天十几年了,就算媒体实锤,再等几个月有错么?粉丝之所以坚持是因...

榆次区会并入太原市吗?

如今的太原虽然是后知后觉,但也有了想要发展的强烈意愿。太原想要发展,首先要在地域上进行扩大,增加人流量。其次还要在制度上做一些改变,比如为创业者提供更多的条件和优惠等,吸引更多的产业、企业和人才。身为一名太原市民,个人希望,未来不仅是榆次,而是整个晋中都可以并入太原。这样,太原的...

如果上天给你一次可以娶女明星的机会,你会选择哪位女明星?

明星我真的不想要,她才是真的美,不知是谁...

艺术画家会给他的老婆或者他孩子画艺术画吗?有什么知名的作品吗?

艺术家第一手的模特资料就是自己的太太和孩子。😏这要说起来例子太多了,我们拿西方几位知名艺术家来举例。印象派大师莫奈先生的人物画多数以他的妻子卡缪为模特。立体派创始人,20世纪影响世界画坛最重要的艺术家毕加索以他的情人们为模特画了很多作品,晚年画了很多以他的爱女为模特的作品。……希...

fengxing1217fengxing1217X_Seven
猜你喜欢
热门推荐
今日推荐 更多
猜你喜欢