斐波那契查找（Fibonacci Search）

斐波那契查找利用斐波那契数列对有序表进行不等比例分割，从而定位目标关键字。与二分查找不同，它将区间分成 F(k-1) 和 F(k-2) 两部分，仅需加减运算，适合外存访问场景。

查找过程

Fibonacci 分割原理

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, …，其中 F(k) = F(k-1) + F(k-2)。

对于大小为 n 的有序数组，找到最小的 k 使得 F(k) ≥ n，将数组补充到 F(k) 大小（末尾补最大值）。每次分割：

• 探针位置：probe = lo + F(k-2) - 1
• 若 A[probe] < target：在右半（F(k-2) 个元素）继续，k = k-2
• 若 A[probe] > target：在左半（F(k-1) 个元素）继续，k = k-1
• 若相等：查找成功

过程模拟

以有序数组 [1, 3, 5, 7, 9, 11, 13]（n=7）、目标 target = 11 为例，F(6)=8≥7：

步骤图：第一次 Fibonacci 分割，probe=F(5)-1=4，A[4]=9＜11 → 查右半

1/3

三种有序表查找策略对比

算法	探针计算	运算	时间复杂度	适用场景
二分查找	(lo+hi)/2 固定取中	加、除	O(log n)	任意有序数组
插值查找	按关键字比例估算	加、乘、除	均匀 O(log log n)	均匀分布数据
斐波那契查找	F(k-2)-1 偏左分割	仅加减	O(log n)	外存/硬件加速

算法特性

• 时间复杂度：O(log n)，与二分查找同阶，常数略有差异。
• 空间复杂度：O(1)，需预先生成 Fibonacci 数列（常数大小）。
• 仅需加减运算：避免乘除法，适合乘除开销大的硬件环境。
• 需要补全数组：将数组补到 F(k) 大小，增加少量空间但不影响正确性。

Baseline 任务：斐波那契查找

任务内容

完成 ordered_search.cpp，实现以下函数：

1. 斐波那契查找 int FibonacciSearch(vector<int>& nums, int target)
   • 利用斐波那契分割思想完成关键字定位
   • 将原数组补充至 F(k) 大小后在区间内迭代
   • 返回目标所在原数组下标，未找到返回 -1

文件结构

• ordered_search.h：函数声明
• ordered_search.cpp：有序表查找核心实现
• test.cpp：测试程序

验证方式

• 编译：g++ -std=c++17 test.cpp ordered_search.cpp -o testOrderedSearch
• 运行：./testOrderedSearch