【数据结构与算法】【查找】斐波那契查找的代码实现

不念不忘少年蓝@ 2022-08-13 15:48 180阅读 0赞

**斐波那契查找**（Fibonacci Search）：基于折半查找，对于mid的选择，使用斐波那契数组进行了调整。

**mid计算公式**：mid = low + F\[k - 1\] - 1

**斐波那契数组计算公式**：

F\[K\] = F \[k - 1\] + F\[K - 2\]

F\[k\] - 1 = (F\[k - 1\] - 1) + 1 + (F\[k - 2\] - 1)

**优劣势分析**：mid左侧的元素个数大于右侧的元素个数。所以，如果要查找的记录在右侧，则左侧的数据就不需要比较了，效率比较高；如果要查找的记录在左侧，则效率比较低。

代码实现：

// Filename: fibonacci_search.c
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include "public.h"
    
    // 计数器，评估性能使用
    extern int count;
    
    // 斐波那契数组
    int F[47];
    void InitF()
    {
        int i;
        F[0] = 0;
        F[1] = 1;
        for (i = 2; i < sizeof(F) / sizeof(int); i++)
        {
            F[i] = F[i - 1] + F[i - 2];
        }
    
        //printf("斐波那契数组: ");
        //PrintArray(F, sizeof(F) / sizeof(int));
        //printf("\n");
        return;
    }
    
    // 插值查找
    // a[n]为待查找数组，a[0]不使用，n为数组长度（不包含a[0]）
    // 查找成功，则返回key所在的地址；查找失败，则返回0
    int FibonacciSearch(int a[], int n, int key)
    {
        int low = 1, high = n, mid, i, k = 0;
        count = 0;
    
        // 计算n位于斐波那契数列的位置
        while (n > F[k] -1)
        {
            k++;
        }
    
        // 将待查找数组的长度不足至F[k]-1长度
        for (i = n + 1; i <= F[k] -1; i++)
        {
            a[i] = a[n];
        }
    
        while (low <= high)
        {
            count++;
            mid = low + F[k -1] -1;
            if (key < a[mid])
            {
                high = mid - 1;
                k = k - 1;
            }
            else if (key > a[mid])
            {
                low = mid + 1;
                k = k - 2;
            }
            else
            {
                if (mid <= n)
                {
                    return mid;
                }
                else
                {
                    return n;
                }
            }
        }
    
        return 0;
    }
    
    // 斐波那契查找主函数
    int FibonacciSearchMain()
    {
        int value;
        int retval;
        int arr[20] = {0xFF, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99, -1};
    
        printf("斐波那契查找演示(a[0]未使用，不参与排序): \n");
    
        printf("静态查找表数据：\n");
        PrintArray(arr, sizeof(arr) / sizeof(int));
        printf("\n");
    
        // 初始化斐波那契数组
        InitF();
    
        while (1)
        {
            // 查找元素
            printf("请输入要查找的数据: \n");
            scanf("%d", &value);
            // 退出查找
            if (0xFF == value) break;
    
            retval = FibonacciSearch(arr, 10, value);
    
            if (0 == retval)
            {
                printf("查找失败! 总计比较次数: %d.\n", count);
            }
            else
            {
                printf("查找成功，元素所在位置: %d. 总计比较次数: %d.\n", retval, count);
            }
        }
    
        return 0;
    }