文档章节

插值查找

laomd
 laomd
发布于 2017/02/24 11:05
字数 1007
阅读 30
收藏 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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

c语言之内存分配笔记

先看一个数组: short array[5] = {1,2} // 这儿定义的一个int类型的数组,数组第1和第2个元素值是1和2.其余后面默认会给值为0; 或者 short array[] = {1,2};//这儿数组第1和第2个元素,数组...

DannyCoder
今天
2
0
Shell | linux安装包不用选择Y/N的方法

apt-get install -y packageOR echo "y" | sudo apt-get install package

云迹
今天
2
0
Hadoop的大数据生态圈

基于Hadoop的大数据的产品圈 大数据产品的一句话概括 Apache Hadoop: 是Apache开源组织的一个分布式计算开源框架,提供了一个分布式文件系统子项目(HDFS)和支持MapReduce分布式计算的软件架...

zimingforever
今天
5
0
八大包装类型的equals方法

先看其中一个源码 结论:八大包装类型的equals方法都是先判断类型是否相同,不相同则是false,相同则判断值是否相等 注意:包装类型不能直接用==来等值比较,否则编译报错,但是数值的基本类型...

xuklc
今天
2
0
NoSQL , Memcached介绍

什么是NoSQL 非关系型数据库就是NoSQL,关系型数据库代表MySQL 对于关系型数据库来说,是需要把数据存储到库、表、行、字段里,查询的时候根据条件一行一行地去匹配,当量非常大的时候就很耗...

TaoXu
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部