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

插值查找(按比例查找)

让编程改变世界

Change the world by program

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

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

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

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

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

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

插值查找

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

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

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

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

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

视频下载

备用视频下载
技术, IT技术, 数据结构和算法, 查找

风险提示及免责条款

市场有风险,投资需谨慎。本文不构成个人投资建议,也未考虑到个别用户特殊的投资目标、财务状况或需要。用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资,责任自负。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场,不承担相关法律责任。如若转载,请注明出处。 如若内容造成侵权/违法违规/事实不符,请点击下方“内容举报”进行投诉反馈!
立即
投稿

微信公众账号

微信扫一扫加关注

返回
顶部