文档章节

插值查找

laomd
 laomd
发布于 2017/02/24 11:05
字数 1007
阅读 32
收藏 0

【为什么需要插值查找】

        先来看看一个实际的例子。假如英语课上,老师叫你在牛津字典里面查 “apple” 这个词。小明同学用线性查找的办法,从第一个‘a’挨个查呀查终于查到了 “apple”,老师说小明你真棒就是有点傻。比小明稍微聪明一点的小美因为学过折半查找,他首先翻到字典一半L的地方,发现哎apple的字典序比L小,好,再在前面折一半,一直这样折呀折,终于,小美也找到了apple,老师说,你也很棒哦!可是还有没有更聪明的同学仔?当然是有的,那就是学过插值查找的小东了哈哈!!!!

        小东是这样找的,他发现a是在整个字典的靠前的部分,于是他没有直接就翻一半,而是先翻开前面的一小部分,从一小部分里面再翻一小部分直到翻到a,一直这样下去,小东很快就找到了apple。老师说,小东你好聪明啊!!

        然后老师又说,我们再查一个“zero”。小明坚持条条大路通罗马的信念一条道走到黑从a翻到了z,最后放学了也没找出来;小美还是按照她的这般,不断折啊折,终于找到了zero,回头一看小东一早就找到了zero。她惊喜地问小东:“小东你好厉害哦,可以教教我你是怎么找得这么快的吗?”侠肝义胆的小东路见不平一声吼,决定英雄救美!!!

【原理】

        思想:通过一个比例来描述具有key值的元素在整个数据串中的大概位置。这是与折半查找的根本区别,折半查找是通过每次缩短一半来夹逼出key值,而插值查找不再是通过缩短一半,而是根据比例来缩短。

下面我们就来看一个example。

        假定有一个1 3 5 7 9 11这样的数组,key = 3。如果是折半,我们应该有这样的代码:

while(low < high)
{
    int mid = low + (high - low) / 2;

    if(v[mid] == key)
        return mid + 1;
    else if(v[mid] < key)
        low = mid + 1;
    else
        high = mid;
}
return 0;

,从而把范围0 ~ 6 --> 0 ~ 3 -->1;

但插值排序是这样的:

while(low < high)
{
    int pos = low + (key - v[low]) * (high - 1 - low) / (v[high] - v[low]);
    //(key - v[low]) / (v[high] - v[low])计算出key值的比例,再乘high - 1 - low就是key值的大概位置了
    if(v[pos] == key)
        return mid + 1;
    else if(v[pos] < key)
        low = pos + 1;
    else
        high = pos;
}
return 0;

,从而范围是0 ~ 6 --> 1,从而减少了很多不必要的折半。

 

        前提条件:

1.数据是已排序

        插值查找算法是对折半查找算法在更强条件(均匀分布)下的改进,也应该具备像折半查找算法一样的前提,就是已排序。通过小东的例子我们也很容易理解这一点,如果字典没有事先排序,那么小东断言a在字典靠前的部分就是不正确的,那么他翻到前面可能根本就找不到apple。

2.数据呈现均匀分布特征 

        根本原因就是插值查找通过比例来缩短查找范围。有一点数学功底的人都知道,计算比例的常用对象是连续量,因为连续,比例自然就可以表示一个量在整个串中的相对位置;至于离散量,只有间距相等时,比例才能准确描述某个值的相对位置。例如,一个1 7 10000 10001 12345 12999 19999 20000 199999 1 100000000这样的几个离散量,按照上面的方法计算20000的相对位置就是0 + (20000 - 1) * (10 - 1  - 1)  / (100000000 - 0) == 0!!!这跟20000的真实相对距离。。。。。。事实上,如果数组不是均匀分布的,插值查找的效率比折半查找还要低。

© 著作权归作者所有

共有 人打赏支持
laomd
粉丝 0
博文 31
码字总数 12000
作品 0
广州
简单的顺序表查找技术java实现

1折半查找技术:简称为二分查找技术。它的前提是,线性表中的记录必须是关键字有序,通常是从小到大有序,线性表必须采用顺序存储。思想:取中间记录为比较对象,若给定值与中间记录的关键字...

liuzhangheng
2014/04/28
0
0
【图像缩放】双立方(三次)卷积插值

前言 图像处理中有三种常用的插值算法: 最邻近插值 双线性插值 双立方(三次卷积)插值 其中效果最好的是,本文介绍它的原理以及使用 如果想先看效果和源码,可以拉到最底部 本文的契机是某...

撒网要见鱼
2017/11/02
0
0
【图像缩放】双立方(三次)卷积插值

前言 图像处理中有三种常用的插值算法: 最邻近插值 双线性插值 双立方(三次卷积)插值 其中效果最好的是,本文介绍它的原理以及使用 如果想先看效果和源码,可以拉到最底部 本文的契机是某...

dailc
07/01
0
0
Python数据分析工具库-Scipy 矩阵支持库

函数库在库的基础上增加了众多的数学、科学以及工程计算中常用的库函数。例如线性代数、常微分方程数值求解、信号处理、图像处理、稀疏矩阵等等。可以进行插值处理、信号滤波以及用C语言加速...

损失函数
05/28
0
0
【图像缩放】双立方(三次)卷积插值

前言 图像处理中有三种常用的插值算法: 最邻近插值 双线性插值 双立方(三次卷积)插值 其中效果最好的是,本文介绍它的原理以及使用 如果想先看效果和源码,可以拉到最底部 本文的契机是某...

撒网要见鱼
2017/11/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【大福利】极客时间专栏返现二维码大汇总

我已经购买了如下专栏,大家通过我的二维码你可以获得一定额度的返现! 然后,再给大家来个福利,只要你通过我的二维码购买,并且关注了【飞鱼说编程】公众号,可以加我微信或者私聊我,我再...

飞鱼说编程
今天
1
0
Spring5对比Spring3.2源码之容器的基本实现

最近看了《Spring源码深度解析》,该书是基于Spring3.2版本的,其中关于第二章容器的基本实现部分,目前spring5的实现方式已有较大改变。 Spring3.2的实现: public void testSimpleLoad(){...

Ilike_Java
今天
1
0
【王阳明心学语录】-001

1.“破山中贼易,破心中贼难。” 2.“夫万事万物之理不外于吾心。” 3.“心即理也。”“心外无理,心外无物,心外无事。” 4.“人心之得其正者即道心;道心之失其正者即人心。” 5.“无...

卯金刀GG
今天
2
0
OSChina 周三乱弹 —— 我们无法成为野兽

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ _刚刚好: 霸王洗发水这波很骚 手机党少年们想听歌,请使劲儿戳(这里) hahahahahahh @嘻酱:居然忘了喝水。 让你喝可乐的话, 你准忘不了...

小小编辑
今天
9
0
vm GC 日志 配置及查看

-XX:+PrintGCDetails 打印 gc 日志 -XX:+PrintTenuringDistribution 监控晋升分布 -XX:+PrintGCTimeStamps 包含时间戳 -XX:+printGCDateStamps 包含时间 -Xloggc:<filename> 可以将数据保存为......

Canaan_
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部