如何编写斐波那契查找算法完整C代码

这篇文章将为大家详细讲解有关如何编写斐波那契查找算法完整C代码，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。

/* 斐波那契查找法 */ #include <stdio.h> #include <stdlib.h> 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<nFib; i++ )	//用最后一个元素来补充数组	b[i] = b[n-1];	low = 0;	high = nFib-1;	mid = low + Fib(k-1)-1;	while( low < mid ) {	//还剩最后两个数的时候,low == mid,可以在循环后处理	if( b[mid] > 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<n; i++ )	scanf("%d", &a[i]);	printf("请输入要查找的关键字:\n");	int key;	int search;	scanf("%d", &key);	search = FibSearch( a, n, key );	if( search >= 0 )	printf("位置%d处查找成功!\n", search);	else	printf("未查找到%d!\n", key);	return 0; }

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

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

关于如何编写斐波那契查找算法完整C代码就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。