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

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

/* 斐波那契查找法 */#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) 如果匹配到最后两个元素，直接让这两个元素与关键字作比较。

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