如何編寫斐波那契查找算法完整C代碼

這篇文章將為大家詳細(xì)講解有關(guān)如何編寫斐波那契查找算法完整C代碼，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。

/* 斐波那契查找法 */

#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 );	//擴(kuò)充數(shù)組的大小

	for( int i=n; i<nFib; i++ )		//用最后一個(gè)元素來補(bǔ)充數(shù)組
		b[i] = b[n-1];
	
	low = 0;
	high = nFib-1;

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

	while( low < mid ) {	//還剩最后兩個(gè)數(shù)的時(shí)候,low == mid,可以在循環(huán)后處理

		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("請輸入目標(biāo)數(shù)組的大小:\n");
	scanf("%d", &n);
	int *a = (int *)malloc(sizeof(int)*n);
	printf("請輸入%d個(gè)有序整數(shù):\n", n);
	for( int i=0; i<n; i++ )
		scanf("%d", &a[i]);
	printf("請輸入要查找的關(guān)鍵字:\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）當(dāng)key=a[mid]時(shí)，查找成功；
  2）當(dāng)key<a[mid]時(shí)，新的查找范圍是第low個(gè)到第mid個(gè)，此時(shí)范圍個(gè)數(shù)為F[k-1]個(gè)；
  3）當(dāng)key>a[mid]時(shí)，新的查找范圍是第mid+1個(gè)到第high個(gè)，此時(shí)范圍個(gè)數(shù)為F[k-2] 個(gè)。

  4) 如果匹配到最后兩個(gè)元素，直接讓這兩個(gè)元素與關(guān)鍵字作比較。

關(guān)于如何編寫斐波那契查找算法完整C代碼就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。