插值查找
博客专区 > laomd 的博客 > 博客详情
插值查找
laomd 发表于1年前
插值查找
  • 发表于 1年前
  • 阅读 25
  • 收藏 0
  • 点赞 0
  • 评论 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的真实相对距离。。。。。。事实上,如果数组不是均匀分布的,插值查找的效率比折半查找还要低。

标签: 查找算法
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 31
码字总数 12000
×
laomd
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: