这是一种和二分比较相似的查找的算法, 不过不同的是, 对于分布比较均匀的较大的数组, 插值查找有时能够一次就搜索到位..
为什么能够这么快呢`? 看网上没有什么关于这种算法的描述, 我就来描述一下吧.
首先要知道一点, 这种搜索方式只能够针对顺序表进行,, 再一个要理解顺序表中的一个特点, 在顺序表中查找是否存在一个值, 此时我可以对顺序表中的任意一个元素进行比较, 如果我要在A中寻找值为t的元素是否存在, 那么我用a[i]和t进行比较, (a[i]可以是顺序表中任意一个元素..), 如果a[i]==t的话, i就是t所在的位置, 如果a[i] > t, 那么说明t一定不在在a[i], a[i+1]....a[n-1], a[n]... 也就是说现在只需要对a[1]..a[i-1]进行搜索即可..
好好理解一下吧, 如果上面的理解不了, 那么插值查找就不好理解..
接下来我用low和high来保存该搜索的范围, 在刚开始low=0, hight=n-1. 设i是在low到high之间的相对位置.. 如: 若 i= 0, low = 0, 那么就该让t和a[i + low]比较, 即判断t是否和a[0]相等..
现在就是要确定i在哪里了..
假设顺序表的分布比较均匀, 那么有下面的方程:
(t - a[low]) : (i + low) = (a[high] - a[low]) : (high - low)
i = (t - a[low]) * (high - low) / (a[high] - a[low]) + low;
差不多了吧...
我的语言表达能力有限, 若还不大理解, 就看代码吧:
/* a是待搜索的顺序表,, size是a的长度, t 是待搜索的值 */
int search(int a[], int size, int t)
{
int low = 0, high = size - 1;
int pos;
while(low <= high){
pos = (t - a[low])/(a[high] - a[low])*(high - low) + low;
if(a[pos] == t){
return pos;
}
if(a[pos] > t){
high = pos - 1;
}else{
low = pos + 1;
}
}
return -1;
}
分享到:
相关推荐
搜索算法:搜索算法用于在数据集中查找特定元素的算法。常见的搜索算法包括线性搜索、二分搜索等。 图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法...
2)源更新:找到一个包含所需源位置的四面体(通过蛮力搜索,或通过有/无八叉树查找的邻接游走); 3) 插值:计算在 2) 中选择的四面体顶点处 HRTF 测量值的线性插值的重心权重 参考: Gamper, H. (2013)。 “方位...
find_cross() 使用搜索和插值的组合来估计因变量 Y 与指定目标级别 y_target 交叉时的 X 值。 如果有多个平交路口, find_cross 会查找所有平交路口。 此函数设计用于处理连续值和离散值 Y。 因此,如果输入序列...
二分搜索插值 查找表进行内插。 BST为其搜索提供了最佳结果。 使用linearinterpolatebst.cpp并将其包含在您的应用程序中。
这些使用二分搜索来定位跨越该点的网格点并立即在那里评估插值,而不是预先计算然后评估整列的分段多项式插值(请参阅“分段多项式微积分”)。 interp1qn2 和 pchipqn2 比两次调用 interp1qn 或 pchipqn 稍快,...
matlab开发-findcrossmversion21。使用搜索和插值组合查找和/或估计平交道口。
针对该问题,提出采用查找表法和两次线性插值的方法计算出方位角校正系数的二次校正实现方法。首先建立全空间误差校正表模型,采用OLE-DB应用接口读取误差校正表并作为DataTable存储;然后根据实际测量的倾角、方位...
这意味着我们的日志不仅将获取纯字符串,还将获取结构化数据,从而使我们能够搜索特定的属性值(例如,搜索OrderId="123"来跟踪某些订单,或者搜索OperationElapsedTime>1000来查找慢速操作) 。 这种方法的问题...
交替进行二进制搜索和插值搜索二分搜索——通过重复将其可能所在的范围减半来找到一个项目Gallop 搜索 — 倾向于查找靠近搜索开始的元素的搜索,查找呈指数增长的范围,然后对包含该项目的范围执行二分搜索插值搜索 ...
本文主要讨论二叉搜索树的基本性质以及基本操作,并用C++代码实现,每个成员... 包括: 普通二叉树的遍历(先序,中序,后序,分层),二叉搜索树的建立,插值,删值,求前驱,求后继,求size,求最大节点,最小节点
[插值查找] [斐波那契查找] [树表查找] [分块查找] [搜索类算法] [设计模式] [创建型] [结构型] [行为型] 数据库 [MySQL] 开源框架 [常用框架] [Motan] [Dubbo] [持久层框架] [版本管理] [SVN] 分布式系统 ...
使用两个查找表,通过逐步搜索法对高光谱遥感数据进行水汽反演,得到水汽含量分布图。结果显示,使用三次样条插值方法得到的辐亮度值与MODTRAN计算结果只有0.1%的误差。对两景机载可见光/红外成像光谱仪(AVIRIS)高...
- 7-3 插值查找 - 7-4 斐波那契查找 - 7-5 稠密索引 - 7-6 分块索引 - 7-7 倒排索引 - 7-8 哈希 -------- 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心...
一般我们在解决问题时候,经常能碰到好几种解决方式...插值搜索算法 是根据要查找的关键字key与顺序表中最大、最小记录的关键字比较后的查找方法,它假设输入数组是线性增加的。 跳跃搜索算法 需要通过固定的跳跃间隔,
查找(搜索)算法:二分查找、插值查找、红黑树等。 Hash表的使用:典型的以空间换时间,速度很快。值得深入思考 动态规划:0-1背包问题,迪杰斯特拉算法,贪心算法等。 图遍历算法:(1) , (2) 二叉树的前中后序遍历...
我的算法我的算法学习笔记数据结构叠放队列链表BinarySearchTree 组地图eep 段树特里联合查找AVL树红黑树哈希表图形演算法分类气泡分选选择排序插入排序贝壳分类快速分类合并排序堆排序计数排序桶分类基数排序搜索二...
插值搜索 数组中的第二个Max 在矩阵上进行二进制搜索 数数X的数组 如果阵列顺时针旋转,则查找最小值 反转对 找出a,b使a + b = X 合并后找到两个排序数组的中位数 图算法 图表示 广度优先搜索 深度优先搜索 拓扑...
求职学习材料 没有重复 希望这会有所帮助 按主题 所有算法 图论的温和介绍– basecs –中 图表简介 图的性质 边列表 ...插值搜索 查找最小/最大的Kth 在数组中查找对 快速排序 检测图中的周期 弗洛伊
附件详细说明了Excel画平滑曲线散点图的...附件的 .mht文件,是一个简单介绍贝塞尔三次插值的文档,可以用IE打开,更多贝塞尔插值的算法,可以用搜索引擎找 附件的 .xls文件,打开以后,会看见三个工作表,分别演示了
附件的 .mht文件,是一个简单介绍贝塞尔三次插值的文档,可以用IE打开,更多贝塞尔插值的算法,可以用搜索引擎找 附件的 .xls文件,打开以后,会看见三个工作表,分别演示了 找一个数值在曲线上的一组对应点 找一个...