上一页我们看到，二分查找很好用，但有个细节：每次比较其实要做一次判断相等、再判断往左还是往右，失败时比了两次。而左右两个分支的宽度还不相等——这遗留问题正是 Fibonacci 查找的切入点。

上页看到二分查找有三次比较：小于、大于、等于。中点命中概率很小，多数时间都在往左或往右走。那这两个方向的代价一样吗？数一数就会发现，左右并不公平。

上页结论：二分的两个分支深度不同，深的那条反而更常被走到。既然访问次数改不了，那就改变分法——把切分点往右挪，让常走的后段变短、变浅，代价自然降下来。

上一页确认切分点要偏后，但偏到哪才恰到好处？把区间按黄金分割 0.618 切开：短段在前、长段在后。而这个比例，恰好能被 Fibonacci 数列越来越精确地逼近。

上一页我们看到，黄金分割能给出最合适的不平衡切分点。可是黄金分割比 0.618 是个无理数，比较时没法直接算——好在 Fibonacci 数列相邻两项之比，恰好会越来越逼近它。

Fibonacci 查找的每一轮：按 fib 数定切分点，比较后向左或向右收缩区间。

用 Fibonacci 数定位切分点 k，按三种比较结果收缩区间，直至命中或区间为空。

切分点取 lo+fib[k-1]，使前段短、后段长；命中右侧时按 fib[k-2] 收缩，两分支代价趋于均衡。

上一页的代码里，切分点靠 fib(k) 定位。但每次查找都从 fib(1) 算到 fib(k) 太浪费——其实整个查找过程中，只需要相邻两个 Fib 数随分支同步推进就够了。

在长度为 12 的有序向量上查找目标，看 Fibonacci 查找如何逐步收缩区间。

从左往右看每个节点：方框内是当前向量宽度（Fib 数），箭头标注切分点 mi 位置，跟随箭头观察左右两支宽度如何递减。

有序向量长 fib(k)-1，在 fib(k-1)-1 处切分后，若目标值大于切分元素，下一步在前段还是后段继续？宽度是多少？

前面我们让切分点偏后，换来了更快的推进速度。但代价是什么？每一次查找走前后分支的概率和代价都不一样，真正要比较的是平均成本，而不是单步快慢。

两者都是有序向量的减治查找，唯一差别在切分点位置——却直接决定比较次数的分布。

上一页比较了两者效率，Fibonacci 查找略胜，但胜在哪里、有没有极限？关键在于：切口偏后让后段更短，比较次数被压到 O(logφn)，而这个比例在数学上恰恰是最优的。

• ✓深层成本在比较次数：转向成功查找，且转向更省，故切分点应偏后
• ✓黄金分割确定比例，Fib 数给出可实现的整数切分点
• ✓实现只用加减推进 fib，避免乘除，分界 case 需留意边界
• ✓平均复杂度同为 O(logn)，但常数更小，且证明其已达最优

三个问题没有唯一答案：先自己想几分钟，再对照参考答案。