查找算法—-插值查找

1. 插值查找：在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不 会从中间开始查起，而是有一定目的的往前或往后翻。同样的，比如要在取值范围1~10000之间100个元素从小到大均匀分布的数组中查找5，我们自然会考虑从。数组下标较小的开始查找。         经过以上分析，折半查找这种查找方式，不是自适应的(也就是说是傻瓜式的)。二分查找中查找点计算如下：mid = (low + high ) / 2，即mid = low + 1 / 2 * ( high - low )。         通过类比，我们可以将查找的点改进为如下：mid = low + ( key-a[low] ) / ( a[high]-a[low] ) = ( high-low )。     
2. 插值查找的的时间复杂度：插值查找的的时间复杂度为O( log( logn ) )

查找算法—-插值查找最先出现在Python成神之路。