/* 斐波那契查找法 */

#include 
#include 

int Fib( int k )
{
	if( 1 == k || 2 == k )
		return 1;
	else
		return Fib(k-1)+Fib(k-2);
}

int FibSearch( int *a, int n, int key )
{
	int k = 1;
	int nFib;
	int *b;
	int low, mid, high;

	while( Fib(k) < n )			//找到Fib[k]
		k++;
	nFib = Fib(k);

	b = (int *)realloc( a, sizeof(int)*nFib );	//扩充数组的大小

	for( int i=n; i key ) {
			k = k - 1;
			high = mid;
		}


		if( b[mid] < key ) {
			k = k-2;
			low = mid+1;
		}

		if( b[mid] == key ) {
			if( mid >= n-1 && mid <= nFib )
				return n-1;
			return mid;
		}

		mid = low + Fib(k-1)-1;

	}

	if( low == key )
		return low;

	return -1;
}

int main()
{
	int n;
	printf("请输入目标数组的大小:\n");
	scanf("%d", &n);
	int *a = (int *)malloc(sizeof(int)*n);
	printf("请输入%d个有序整数:\n", n);
	for( int i=0; i= 0 )
		printf("位置%d处查找成功!\n", search);
	else
		printf("未查找到%d!\n", key);

	
	return 0;
}

本代码中斐波那契查找的核心是：
  1）当key=a[mid]时，查找成功；
  2）当keya[mid]时，新的查找范围是第mid+1个到第high个，此时范围个数为F[k-2] 个。

  4) 如果匹配到最后两个元素，直接让这两个元素与关键字作比较。