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