文档章节

插值查找

laomd
 laomd
发布于 2017/02/24 11:05
字数 1007
阅读 47
收藏 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
广州
私信 提问
(8)《数据结构与算法》之查找算法

在java中,我们常见的查找有四种 顺序查找,也叫线性查找 二分查找,也叫折半查找 插值查找 斐波那契查找 我们将一一介绍着四种查找方式的思想以及程序的实现。 1.顺序查找 顺序查找 的查找过...

行走在代码边缘
06/21
0
0
简单的顺序表查找技术java实现

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

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

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

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

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

dailc
02/18
0
0
Swift 5—表达通过字符串插值

Swift的设计 - 首先是 - 是一种安全的语言。检查数字和集合是否有溢出,变量总是在第一次使用之前初始化,选项确保正确处理非值,并且相应地命名任何可能不安全的操作。 这些语言功能在很大程...

久遇而安
06/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring使用ThreadPoolTaskExecutor自定义线程池及实现异步调用

多线程一直是工作或面试过程中的高频知识点,今天给大家分享一下使用 ThreadPoolTaskExecutor 来自定义线程池和实现异步调用多线程。 一、ThreadPoolTaskExecutor 本文采用 Executors 的工厂...

CREATE_17
今天
5
0
CSS盒子模型

CSS盒子模型 组成: content --> padding --> border --> margin 像现实生活中的快递: 物品 --> 填充物 --> 包装盒 --> 盒子与盒子之间的间距 content :width、height组成的 内容区域 padd......

studywin
今天
7
0
修复Win10下开始菜单、设置等系统软件无法打开的问题

因为各种各样的原因导致系统文件丢失、损坏、被修改,而造成win10的开始菜单、设置等系统软件无法打开的情况,可以尝试如下方法解决 此方法只在部分情况下有效,但值得一试 用Windows键+R打开...

locbytes
昨天
8
0
jquery 添加和删除节点

本文转载于:专业的前端网站➺jquery 添加和删除节点 // 增加一个三和一节点function addPanel() { // var newPanel = $('.my-panel').clone(true) var newPanel = $(".triple-panel-con......

前端老手
昨天
8
0
一、Django基础

一、web框架分类和wsgiref模块使用介绍 web框架的本质 socket服务端 与 浏览器的通信 socket服务端功能划分: 负责与浏览器收发消息(socket通信) --> wsgiref/uWsgi/gunicorn... 根据用户访问...

ZeroBit
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部