斐波那契查找
入门它和二分类似，但区间分割点来自斐波那契数列。
// 搜索输入
定义数组和目标值
可视化演示开发中
斐波那契查找 的交互式动画即将上线，敬请期待。
1int fibonacciSearch(int arr[], int n, int target) {
2 int fibMm2 = 0, fibMm1 = 1, fibM = fibMm1 + fibMm2;
3 while (fibM < n) {
4 fibMm2 = fibMm1;
5 fibMm1 = fibM;
6 fibM = fibMm1 + fibMm2;
7 }
8 int offset = -1;
9 while (fibM > 1) {
10 int i = min(offset + fibMm2, n - 1);
11 if (arr[i] < target) {
12 fibM = fibMm1;
13 fibMm1 = fibMm2;
14 fibMm2 = fibM - fibMm1;
15 offset = i;
16 } else if (arr[i] > target) {
17 fibM = fibMm2;
18 fibMm1 = fibMm1 - fibMm2;
19 fibMm2 = fibM - fibMm1;
20 } else {
21 return i;
22 }
23 }
24 if (fibMm1 && offset + 1 < n && arr[offset + 1] == target) return offset + 1;
25 return -1;
26}
复杂度分析
时间 O(log n)
空间 O(1)
最优 O(1)
最坏 O(log n)
算法讲解
斐波那契查找先找到一个不小于数组长度的斐波那契数，再据此决定每一轮的探测位置。
它和二分查找一样都在不断缩小区间，但分割比例来自斐波那契数列，而不是固定的 1/2。
在动画中可以重点观察 offset 和 probe 的变化，它们共同描述了"已经排除到哪里"和"下一次看哪里"。
这类查找方式在历史上与顺序存储、磁盘访问模型和尽量减少除法运算的场景有较强关联。
从教学角度看，它非常适合作为"二分思想的变体"来理解：核心仍是缩区间，只是切分方式不同。
时间复杂度为 O(log n)，空间复杂度为 O(1)。