当前位置:鱼C工作室 >数据结构和算法 > 查看文章

插值查找(按比例查找)- 数据结构和算法70

插值查找(按比例查找)

 

让编程改变世界

Change the world by program


 

上节课小甲鱼给大家介绍了最朴素的查找方法:顺序查找法,原理非常简单,就是迭代目标的每一个元素去跟关键词进行匹配,匹配成功则查找成功。

 

顺序查找算法的时间复杂度是O(n),不算太好,也不能再差了。那有没有更好的查找算法呢?

那是必须的!我们接下来继续介绍效率更高的方法,也是属于静态查找的范畴。

 

我们从现实中来找找灵感吧:

 

话说有一天,小甲鱼突发奇想,要回顾下我国的古代四大奇书,大家应该没人不知道四大奇书是什么吧?四大奇书就是:“宝哥哥的金箍棒让潘金莲乐不思蜀。”,于是小甲鱼就跑到了当地的图书馆……

 

…… 省略,具体请看视频讲解 ……

 

插值查找

 

现在我们的新问题是,为什么一定要折半呢,而不是四分之一或者折更多呢?

打个比方,在牛津词典里你要查找“apple”这个单词,你会首先翻开字典的中间部分,然后继续折半吗?这样不是有点儿犯傻吗?

 

查找单词“apple”,我们肯定是下意识的往字典的最前部分翻去,而查找单词“zero”则相反,我们会下意识的往字典的最后部分翻去。

鉴于这种常识,我们的科学家们认为也可以在折半查找法的基础上进行改造改造,因此就诞生了插值查找法,当然我觉得叫“按比例查找法”好像更合适。

 

…… 省略,具体请看视频讲解 ……


为您推荐

报歉!评论已关闭.