上一页我们说要改进二分查找，那先回到原版长什么样：每次取区间中点比一下，根据结果三分岔——相等就中、太小往右、太大往左。看清它的比较方式和区间收缩，才知道哪里值得动手。

把基础版二分查找的每步比较摊开算账，暴露转向次数是隐藏的代价。

前面算过：版本 A 每深入一层要比两次——先问大小，再确认相等。可相等是极小概率事件，第二次比较岂不是白做了？

顺着箭头看：每个节点是一次判断，两条边只做一次比较，区间随之向左或向右收缩。

C++ 代码展示版本 B：三分支合并为两分支，全靠循环不变式。

循环条件 1 < hi-lo 保证区间宽度递减仍可继续；第4行把相等并入右分支，用 hi=mi / lo=mi 保持不变式 A[lo]<=e<A[hi]。

版本 A 失败时只答「没找到」，白跑一趟。版本 B 约定：不管中不中，都返回位置 mi。那失败时这个 mi 是什么？得把语义说清楚，调用方才能放心用。

两个版本形似神异：比较次数从 1+x 降到 1，但语义和后继成本都变了，容易混。

前页对比表已经显示：版本 B 平均省了比较次数，但仔细看两栏——命中左侧时每次都要深度比较，右侧却常一眼即中。省下的次数不等于省下的时间，这份「偏科」值得深挖。

版本 B 按几何中点切，每次比较却代价不同——往深了猜一次很便宜，往浅了猜一次很贵。既然比较代价不均，为何不按代价均分区间？这就是 fib 式划分的出发点。

从入口区间出发，每轮按 fib 比例取 mi、只做一次比较，再深入左半或右半，循环至区间宽度为 1。

版本 C 的代码：fib 式划分点如何计算与分支。

划分点不再取中点，而按 fib(k-1) 偏移；向左走只需多算 fib(k-2)，右侧 fib 更短——用加法换掉除法。

前面三个版本的代码都写出来了，但「能跑」不等于「算得对」。这一页我们换个视角：不逐个试例子，而是找到一个贯穿全程的不变量，一次性证明版本 C 必然正确终止。

A、B 都靠元素比较决定走向，C 却靠减法划界——两者语义与代价结构截然不同，值得系统对照。

在有序向量上查找目标 e，若有多个命中位置，要求返回最靠后的那个，应选用哪个版本及理由？

• ✓查找区间的语义决定了边界写法：往右缩进才安全
• ✓中点后移一位，最坏情况从 log n+1 降一档
• ✓fib 划分只用加减比较，代价换常数收益
• ✓正确性靠不变式：目标始终落在 (lo, hi) 之内
• ✓对比版本是收敛起点：三分支减到两分支是主线

先自己想一阵，再看参考答案——答案只是起点。