插值查找(按比例查找)- 数据结构和算法70
插值查找(按比例查找)
让编程改变世界
Change the world by program
上节课小甲鱼给大家介绍了最朴素的查找方法:顺序查找法,原理非常简单,就是迭代目标的每一个元素去跟关键词进行匹配,匹配成功则查找成功。
顺序查找算法的时间复杂度是O(n),不算太好,也不能再差了。那有没有更好的查找算法呢?
那是必须的!我们接下来继续介绍效率更高的方法,也是属于静态查找的范畴。
我们从现实中来找找灵感吧:
话说有一天,小甲鱼突发奇想,要回顾下我国的古代四大奇书,大家应该没人不知道四大奇书是什么吧?四大奇书就是:“宝哥哥的金箍棒让潘金莲乐不思蜀。”,于是小甲鱼就跑到了当地的图书馆……
…… 省略,具体请看视频讲解 ……
插值查找
现在我们的新问题是,为什么一定要折半呢,而不是四分之一或者折更多呢?
打个比方,在牛津词典里你要查找“apple”这个单词,你会首先翻开字典的中间部分,然后继续折半吗?这样不是有点儿犯傻吗?
查找单词“apple”,我们肯定是下意识的往字典的最前部分翻去,而查找单词“zero”则相反,我们会下意识的往字典的最后部分翻去。
鉴于这种常识,我们的科学家们认为也可以在折半查找法的基础上进行改造改造,因此就诞生了插值查找法,当然我觉得叫“按比例查找法”好像更合适。
…… 省略,具体请看视频讲解 ……
备用视频下载
技术, IT技术, 数据结构和算法, 查找