斐波那契查找
在介绍斐波那契查找之前我们要先了解两件事，黄金分割和斐波那契数列，二者是啥关系。
首先是黄金分割（也叫黄金比例），这个词经常出现在一些建筑物的设计，黄金分割的近似值是0.618。斐波那契数列又称黄金比例数列，指的是这样的数列：1、1、2、3、5、8、13、21、34……，这个数列从第三项开始，每一项都等于前两项之和（F[K] = F[K-1] + F[K-2]）；随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以把黄金比例运用到查找当中。
斐波那契查找依旧基于数组是有序数组，并使数组长度与斐波那契数组元素相匹配，之后类似于二分查找。
斐波那契查找总共分为以下几步：
1.构建斐波那契数列
2.计算数组长度对应的斐波那契数列元素个数
3.对数组进行填充
4.循环进行区间分割，查找中间值
5.判断中间值和目标值的关系，确定更新策略
首先构建斐波那契数列
计算数组长度对应的斐波那契数列元素个数
假设手中的数据如下：
目前数组中的15个元素均不对应斐波那契数列中的F[n]，这种情况就使用策略“大于数组长度的最近一个斐波那契数值”，当前数组的最大值是18，斐波那契数列中大于18的最近元素为21。
对数组进行填充
确定了斐波那契数值之后，将数组第18位到21位进行填充，使用最大值进行填充，即18位到21位均为18。
循环进行区间分割，查找中间值
这一步和二分查找很相似，都是不断缩小范围查找中间值Mid，斐波那契查找中mid的公式如下：
Low + F[K-1]-1
中间值和目标值的关系分为三种
1)相等
数列中存在目标值；
2)目标值大于中间值
新的查找范围在mid+1到第high个，此时范围个数为F[K-2]-1个，即数组右边的长度，所以要在[low,F[k-2]-1]范围查找；
3)目标值小于中间值
重新确定查找范围，新的查找范围是第low个到第mid-1个，此时范围个数为F[K-1]-1个，即数组左边的长度，所以要在[low,F[k-1]-1]范围查找；
#include<stdio.h>
#define MAXSIZE 20
void fibonacci(int *f) //构建斐波那契序列
{
f[0] = 1;
f[1] = 1;
for(int i = 2; i < MAXSIZE; ++i)
f[i] = f[i - 2] + f[i - 1];
}
int fibonacci_search(int *a,int key,int n)
{
int low = 0,high = n - 1;
int mid = 0;
int k = 0;
int F[MAXSIZE];
fibonacci(F);
while(n > F[k] - 1) //计算出n在斐波那契中的位置
{
++k;
}
for(int i = n; i < F[k] - 1; ++i) //把数组补全，使用a[n-1]
a[i] = a[high];
while(low <= high){
mid = low + F[k-1] - 1; //根据斐波那契数列进行黄金分割
if(a[mid] > key){
high = mid - 1;
k = k - 1;
}
else if(a[mid] < key){
low = mid + 1;
k = k - 2;
}
else{
if(mid <= high) //如果为真则找到相应的位置
return mid;
else
return -1;
}
}
return -1;
}
int main()
{
int a[MAXSIZE] = {5,15,19,20,25,31,38,41,45,49,52,55,57};
int k = 9;
int pos = fibonacci_search(a,k,13);
if(pos != -1)
printf("在数组的第%d个位置找到元素:%d\n",pos + 1,k);
else
printf("未在数组中找到元素:%d\n",k);
return 0;
}
