小甲鱼 发表于 2013-10-26 20:21:23

插值查找法（按比例查找法）

插值查找法（按比例查找法）是在 折半查找算法 的基础上演变而来。

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

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

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

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

想一下：我们之所以知道“apple”这个单词位于字典的很前一部分，是因为“apple”这个单词是以“a”开头的，而“a”这个字母在26个字母里排第一位，而“zero”这个单词的“z”在26个字母里排最后一位，所以我们知道要找“zero”这个单词肯定从字典最后开始找比较快。

那么根据这么个原理，我们就衍生出了插值查找方法：就是按照一定得比例去修改每次分割的值，所以在折半查找法的代码上，我们只需要修改mid的求值算法即可。
   
   
视频讲解：http://blog.fishc.com/2933.html
   
源代码参考：http://bbs.fishc.com/thread-39461-1-1.html


福禄娃娃 发表于 2013-10-26 21:37:56

昨天看到你回了这么一句话志之所趋。无远勿届。穷山复海不能限也。志之所向，无坚不入。锐兵固甲，不能御也。
果断觉得鱼大文学功底深厚，我查了谷歌才知道是啥意思。

小甲鱼 发表于 2013-10-27 16:19:05

福禄娃娃 发表于 2013-10-26 21:37 static/image/common/back.gif
昨天看到你回了这么一句话志之所趋。无远勿届。穷山复海不能限也。志之所向，无坚不入。锐兵固甲，不能御也 ...

{:5_106:}哥们活跃度好高！

岁月如歌 发表于 2013-11-15 23:51:20

真是难得给力的帖子啊。

岁月如歌 发表于 2013-11-17 13:39:51

楼主加油，鱼C加油！我们都看好你哦！

岁月如歌 发表于 2013-11-22 12:57:39

福禄娃娃 发表于 2013-10-26 21:37 static/image/common/back.gif
昨天看到你回了这么一句话志之所趋。无远勿届。穷山复海不能限也。志之所向，无坚不入。锐兵固甲，不能御也 ...

真是难得给力的帖子啊。

岁月如歌 发表于 2013-11-22 18:48:03

楼主加油，鱼C加油！我们都看好你哦！

岁月如歌 发表于 2013-11-24 19:35:33

激动人心，无法言表！

一世安 发表于 2014-9-3 09:54:07

:lol:

zhangzhilin 发表于 2015-3-23 08:59:59

小甲鱼，哪个中间结点的求解没有理解了啊:cry
页: [1]
查看完整版本: 插值查找法（按比例查找法）