费氏（Fibonacci）查找算法类似于二分法查找，使用费氏数列1、2、3、5、8、13、…构成的数列，对有序数列进行分割，然后完成查找。

费氏查找算法的思想如下所述。

假设有序数列为有n个数组元素的数组a[]，且n小于某个Fibonacci数fib（k），数组元素的值设为递增，要查找值为value的数。费氏查找的步骤为：

1）先将fib（k-1）-1作为数列的分割中点，分割为左右两个子数列。

如数组data有20个元素，fib（7）=21＞20，k=7，这时取f0=fib[k-1]=fib[6]=13，取下标为f0-1的元素作为分割中点，也就是将数组元素a[12]作为分割中点。

2）当分割中点的值与要查找的值value相同时（a[f0-1]==value）查找成功，返回中点位置的值f0-1。

3）如果value＜a[f0-1]，表示要查找的数在左边的子数列；否则，在右边的子序列。

4）将子数列作为一个新的序列，重新按Fibonacci数进行分割，直到找到数值为止。当分割的边界值为0时，表示没有找到。(www.daowen.com)

程序在重新分割时，利用了Fibonacci有fib（k）=fib（k-1）+fib（k-2）的特点进行计算。和二分法查找相比，费氏查找效率要高些。因为二分法必须使用除法进行区间的划分，而费氏查找只要用加减法就可以进行区间划分，其计算速度要高。

【例9-16】使用费氏查找算法，在整型数组中查找指定数值的位置。

程序思路：费氏查找算法需要解决如下几个问题。

1）求出Fibonacci数列，并根据数组元素的个数，确定第一个分界点。

2）根据Fibonacci数列的特点，重新计算新的分界点。

程序运行结果：

18