文档章节

插值查找

laomd
 laomd
发布于 2017/02/24 11:05
字数 1007
阅读 34
收藏 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的真实相对距离。。。。。。事实上,如果数组不是均匀分布的,插值查找的效率比折半查找还要低。

© 著作权归作者所有

共有 人打赏支持
上一篇: 斐波那契查找
下一篇: kmp算法
laomd
粉丝 0
博文 31
码字总数 12000
作品 0
广州
私信 提问
简单的顺序表查找技术java实现

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

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

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

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

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

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

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

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

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

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

没有更多内容

加载失败,请刷新页面

加载更多

Linux下端口转发工具rinetd介绍

linux下简单好用的工具rinetd,实现端口映射/转发/重定向,针对TCP协议,不支持UDP。 官网地址 http://www.boutell.com/rinetd 里面介绍及使用齐全。 使用场景举例: 阿里云内网Redis连接问题...

ouhoo
13分钟前
1
0
Oracle学习日志-5(算数运算符,比较运算符和逻辑运算符)

因为有编程基础,所以对于这一章还是很好理解,只需要注意对NULL的运算。 操作的表格 算数运算符 查询商品名字和商品售价,并商品售价乘2 SELECT product_name,sale_price * 2 AS "sale_pri...

白话
25分钟前
1
0
搜索引擎(Lucene介绍、分词器详解)

Lucene介绍 Lucene简介 最受欢迎的java开源全文搜索引擎开发工具包。提供了完整的查询引擎和索引引擎,部分文本分词引擎(英文与德文两种西方语言)。Lucene的目的是为软件开发人员提供一个简...

这很耳东先生
30分钟前
0
0
quartz详细介绍

quartz常用api Scheduler 调度程序交互的主要API。 Job 希望由调度程序执行的组件实现的接口。 JobDetail 用于定义作业的实例。 JobDataMap 可以包含不限量的序列化数据,在job运行的时候可以...

大笨象会跳舞吧
30分钟前
1
0
kotlin使用jackson序列化enum

默认情况下,我们序列化与反序列化enum是它的name,事实上大部分情况下我们需要序列化的是我们自定义的value,那应该怎么做呢? 这种情况下我们就需要@JsonValue与@JsonCreator data class U...

weidedong
35分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部