斐波那契查找（黄金分割法查找)

要想能够理解这一算法，需要先了解
1.二分查找
https://blog.csdn.net/qq_35423154/article/details/101383518
2.斐波那契数
https://blog.csdn.net/qq_35423154/article/details/101684466

黄金分割具有严格的比例性、艺术性、和谐性，蕴藏着丰富的美学价值，这一比值能够引起人们的美感，被认为是建筑和艺术中最理想的比例。


蒙娜丽莎，断臂的维纳斯，这些我们经常见到的艺术品就是采用了黄金分割法，即0.618的比例。

而我们所熟知的斐波那契数列又叫做黄金分割数列，当它无限往下增加时，越到后面两个数的比例就越来越接近0.618即黄金分割点。
在我们眼里，编程也是一种艺术，那么我们能否利用这个万能的黄金分割法，运用到查找中呢？答案是肯定的，我们将斐波那契数与二分查找相结合，就得到了斐波那契查找，它与二分查找的思路相同，但是借助斐波那契数，可以仅仅使用加减法来完成查找，大大提高了效率。

那我们该如何实现呢？
例如我们要在

	int a[] ={1,3,5,7,9,11,13,15,17,19};

查找这个17
首先我们需要找到这个数组的长度n在斐波那契数中的位置

它所处的位置是斐波那契数列中的第七位，而a中只有10个元素，而斐波那契的第七个数为13，所以我们需要补全数组，将数组补充至13-1位，补充的值为最后一项的值


如果我们的key值小于mid的时候，我们按照上图，结合二分查找的思想，我们取到左边的一块，斐波那契数下标减1，我们的high值变为mid-1
而如果当key值大于mid的时候我们取到右边的一块，斐波那契数下标减2，我们的low值变为mid + 1

当我们的mid<=n时，说明mid即为我们查找到的下标。
当mid>n时，说明这个时候我们的mid为补全的下标，我们只需要返回一个原数组的最大下标就可以

完整代码：

#include<stdio.h>
#define MAXSIZE 100
void GitFib(int* fib)
{
	int i;
	fib[0] = 0;
	fib[1] = 1;
	for(i = 2; i < MAXSIZE; i++)
	{
		fib[i] = fib[i - 1] + fib[i - 2];
	}
} 
int FibonacciSearch(int *a,int n,int key)
{
	int i,mid,low=0,high= n ,k=0;
	int fib[MAXSIZE] = {0};
	GitFib(fib); 
	while (n > fib[k] - 1)
	{
		k++;
	}
	//找出n在斐波那契数中的位置 
	for (i = n; i<fib[k] -1; i++)
	{
		a[i] = a[n];
	}
	//补全数组 
	while (low <= high)
	{
		mid = low + fib[k-1] - 1;
		if (key <= a[mid])
		{
			high = mid - 1;
			k -= 1;
		}
		else if (key > a[mid])
		{
			low = mid + 1;
			k -= 2;
		}
		else
		{
			if (mid <= n)
				return mid;
			else
				return n; 
		}
	}
}
int main()
{
	int a[] ={1,3,5,7,9,11,13,15,17,19};
	int key,i,n;
	n = sizeof(a)/sizeof(a[0])-1;
	printf("请输入要查找的数据:");
	scanf("%d",&key);
	printf("%d\n",FibonacciSearch(a,n,key));
	
	return 0;
}

插值查找，斐波那契查找都是二分查找的一种变式，它们的本质上的不同时分隔点的选择不同，实际使用的时候根据数据的综合特点考虑再进行选择