斐波那契搜索详解（C语言实现高效查找算法）

斐波那契搜索 vs 二分搜索

你可能熟悉二分搜索，它每次将数组对半分。而斐波那契搜索则使用斐波那契数来确定分割点，其优势在于：只使用加法和减法（不涉及除法），在某些硬件上效率更高。

算法原理

假设我们要在一个长度为 n 的升序数组中查找目标值 key。步骤如下：

1. 找到最小的斐波那契数 F(m)，使得 F(m) ≥ n + 1。
2. 将原数组扩展至长度 F(m) - 1（不足部分用最大值填充）。
3. 设 offset = -1，i = F(m-2) - 1。
4. 比较 arr[i] 与 key：
• 若相等 → 找到目标，返回索引。
• 若 arr[i] < key → 在右子区间搜索，更新 offset 和斐波那契索引。
• 若 arr[i] > key → 在左子区间搜索，更新斐波那契索引。
5. 重复直到找到或搜索区间为空。

C语言实现

下面是完整的 C 语言代码实现，包含注释帮助你理解每一步：

#include <stdio.h>// 斐波那契搜索函数int fibonacciSearch(int arr[], int n, int key) {    // 初始化斐波那契数    int fibMMm2 = 0; // (m-2)'th Fibonacci number    int fibMMm1 = 1; // (m-1)'th Fibonacci number    int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci number    // 找到最小的 fibM >= n    while (fibM < n) {        fibMMm2 = fibMMm1;        fibMMm1 = fibM;        fibM = fibMMm2 + fibMMm1;    }    // 标记已消除范围的起始偏移量    int offset = -1;    // 当还有元素需要检查时    while (fibM > 1) {        // 检查 fibMMm2 是否为有效位置        int i = (offset + fibMMm2 < n - 1) ? offset + fibMMm2 : n - 1;        if (arr[i] < key) {            // key 在右侧            fibM = fibMMm1;            fibMMm1 = fibMMm2;            fibMMm2 = fibM - fibMMm1;            offset = i;        } else if (arr[i] > key) {            // key 在左侧            fibM = fibMMm2;            fibMMm1 = fibMMm1 - fibMMm2;            fibMMm2 = fibM - fibMMm1;        } else {            return i; // 找到目标        }    }    // 比较最后一个元素    if (fibMMm1 && offset + 1 < n && arr[offset + 1] == key) {        return offset + 1;    }    return -1; // 未找到}// 测试主函数int main() {    int arr[] = {10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100};    int n = sizeof(arr) / sizeof(arr[0]);    int key = 85;    int result = fibonacciSearch(arr, n, key);    if (result != -1) {        printf("元素 %d 在索引 %d 处找到。\n", key, result);    } else {        printf("元素 %d 未找到。\n", key);    }    return 0;}

时间复杂度分析

斐波那契搜索的时间复杂度为 O(log n)，与二分搜索相同。但在实际应用中，由于避免了除法运算，它在某些场景下性能更优。

总结

通过本教程，你已经掌握了斐波那契搜索的基本原理和C语言实现方法。这是一种优雅且高效的数据结构教程中常提到的查找技术。虽然现代编程中二分搜索更常用，但理解斐波那契搜索有助于拓宽你的算法视野，尤其在学习高效查找算法时非常有价值。

动手试试吧！修改数组和查找值，观察程序输出，加深理解。