python贝塞尔插值公式_斐波那契查找原理——附python和C++实现

在正式介绍斐波那契查找之前，首先要知道什么是斐波那契数列：

前面的文章分析了顺序查找、二分查找和插值查找，其中顺序查找的思想最简单，只需要将目标值和数据中每一个值进行比较即可；二分查找每次将区间长度缩减一半；插值查找按照目标值和边界值的关系确定区间分割方式。

斐波那契查找同样是查找算法家族中的一员，它要求数据是有序的（升序或降序）。斐波那契查找采用和二分查找/插值查找相似的区间分割策略，都是通过不断的分割区间缩小搜索的范围。

要点：斐波那契数和数据有什么关系？

斐波那契数列中(上表来自维基百科)，从第三项开始，每一项都等于前两项之和：

上述性质可以用于数据区间分割，将一个长度为F(n)数组看做前后两半，前面一半长度是F(n-1)，后面一半的长度是F(n-1)。正是这个想法将斐波那契数列和数组联系到一起，也是后面分析的基础：

其中n的取值是任意长度的，即对任意长度的数组都能找到对应的斐波那契数，下面将具体介绍斐波那契查找的步骤。

1、原理分析

斐波那契查找的整个过程可以分为：

• 构建斐波那契数列；
• 计算数组长度对应的斐波那契数列元素个数；
• 对数组进行填充；
• 循环进行区间分割，查找中间值；
• 判断中间值和目标值的关系，确定更新策略；

1.1 构建斐波那契数列

这一步骤见前面的文章，构建斐波那契数列如下：

[

1.2 计算数组长度对应的斐波那契数列元素个数

假设手中的数据如下：

[

可知上述数据共25个元素，不对应1.1节中的斐波那契数列中任何F(n)，这种情况是很常见的。此时，策略是采用“大于数组长度的最近一个斐波那契数值”。比如当前数组长度为25，斐波那契数列中大于25的最近元素为34。

1.3 对数组进行填充

确定了斐波那契数值后，就要进行数值填充，即将数组从25个元素填充到34个。填充时，将第26到34个元素均采用第25个元素值进行填充，即最大值填充。

1.4 循环进行区间分割，查找中间值

这一个步骤与前面介绍的二分查找和插值查找相似，都是不断的缩小搜索区间，进而确定目标值的位置。区间分割公式如“要点”所述，每次分割中间位置的计算如下：

此时数组被分割为左右两个区间，左边区间含有F(n-1)个元素，-1是因为下标从0开始（比如F(1)表示两个元素）。

1.5 判断中间值和目标值的关系，确定更新策略

中间值和目标值有三种大小关系，分别对应三种处理方式：

• 相等，则查找成功，返回中间位置即可；
• 中间值小于目标值，则说明目标值位于中间值到右边界之间（即右区间），右区间含有F(n-2)个元素，所以n应该更新为n=n-2；
• 中间值大于目标值，这说明目标值位于左边界和中间值之间（即左区间），左区间含有F(n-1)个元素，所以n应更新为n=n-1；

2、python实现

（1）实现过程中，如果数据是列表，则必须首先进行深度复制，因为填充过程会更改原始数据；

（2）因为预先不知道需要多少个斐波那契数值，所以使用max_size先构造一个较多斐波那契数值；

import 

3、C++实现

int 

4、总结

折半查找需要进行除法，插值查找需要进行更复杂的乘法和除法，而斐波那契查找只需要使用加法和减法，在数据量较大时优势更明显。

参考：

【1】https://github.com/el1ven/Fibonacci_Search