Today：给我10分钟，讲明白斐波那契

今天我们来学习斐波那契查找算法，之前学习它的时候自己是花了大约1个小时，算是慢了些。总结了下，这是因为看到的学习资料每个都讲了一些点，最后结合多份资料才搞明白原来是这样，其实如果资料更有逻辑些不用花上1个小时。

因此，我整理后来讲一下，

期待10分钟就可以让你明白。

一、认识斐波那契数列：

斐波那契数列也称为“兔子数列”。它的重要性体现在相邻两数之比趋向黄金分割数，自然界很多现象也可找到它的身影，画图还与漂亮的螺旋线有关。定义式为：

通过Python- SymPy 库中提供的 Fibonacci类，可以直接生成斐波那契数列：

可以看到，该数列该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。

二、斐波那契查找算法：

斐波那契查找算法就是在二分查找的基础上根据斐波那契数列进行分割的。我们来举例说明。现有一个需求：

从data=[0, 1, 16, 24, 35, 48, 59, 62, 73, 88, 99]，找到24所在的位置（即索引号），则有——

1. 构建斐波那契数列。构建到哪一个数值呢？策略是采用“大于数组长度的最近一个斐波那契数值”。比如当前data数列长度（元素个数）为11，斐波那契数列中大于11的最近元素为13。则构建斐波那契数列如下，F[0]=0,F[1]=1,……,F[6]=8, F[7]=13：

2. 扩充data列表。确定了斐波那契数值后，就要进行数值填充，即将数组从11个元素填充到12个（F[7]-1)。填充时，将第12个元素采用第11个元素值进行填充，即最大值填充。得到扩展后的data数列：

3. 数据分区与判断。此时斐波那契数列的数值13-1等于新数列的元素个数。如果是二分法查找，那我们知道以mid=中位数=48区分左右区间，如：

而以斐波那契查找就是以斐波那契数列的规律将左右区间不均等分割，可以定义：

mid=low+F[k - 1] – 1

3.1 这里第一步分区时，low=F[0]=0，k取7（第一步时取构造的斐波那契数列索引最大值，所以是7）。F[k-1]-1= F[7-1]-1=7，即mid=7，会以索引为7对应的值62来区分左右区间：

3.2 将待查值24与62比较，因24<62，则缩小范围至：

3.3 在缩小的范围内（左区间），重新计算mid= low+F[k - 1] – 1。此时low还是=F[0]=0（左区间low不会变化），k取6（范围缩小，k要下降，是左区间则每次下降1，是右区间则每次下降2），F[k-1]-1= F[6-1]-1=4，则mid=4，即按照索引4对应的值35来区分左右区间：

3.4 将待查值24与35比较。因24<35，则缩小范围至：

3.5 在缩小的范围内（左区间），重新计算mid= low+F[k - 1] – 1=0+2=2（low不变，k取5）。即按照索引2对应的值16来区分左右区间：

3.6 将待查值24与16比较。因24>16，则缩小范围至：

3.7 注意此时算法未结束，在缩小的范围（此时为右区间）中，重新计算mid= low+F[k - 1] – 1 。low=mid + 1=3（右区间low=mid+1，需要提高下限），k取3（右区间，k每次下降2），mid=3+1-1=3，即索引3对应的值就是24，与待查值24相等：

找到了待查值24的位置为3，算法结束。

三、Python代码实现

看懂了算法的原理介绍，代码就是算法的具现，如果还没有完全理解透，那可以结合代码反向推导，也能帮助理解：

运行结果，具体为：

【今天就讲到这里，每天进步一点点】