0001 #include "fibonacci/Fib.h" //引入Fib数列类
0002 //Fibonacci查找算法（版本A）：在有序向量的区间[lo, hi)内查找元素e，0 <= lo <= hi <= _size
0003 template <typename T> static Rank fibSearch( T* S, T const& e, Rank lo, Rank hi ) {
0004    //用O(log_phi(n = hi - lo)时间创建Fib数列
0005    for ( Fib fib( hi - lo ); lo < hi; ) { //Fib制表备查；此后每步迭代仅一次比较、两个分支
0006       while ( hi - lo < fib.get() ) fib.prev(); //自后向前顺序查找（分摊O(1)）
0007       Rank mi = lo + fib.get() - 1; //确定形如Fib(k)-1的轴点
0008       if      ( e < S[mi] ) hi = mi; //深入前半段[lo, mi)继续查找
0009       else if ( S[mi] < e ) lo = mi + 1; //深入后半段(mi, hi)继续查找
0010       else                  return mi; //在mi处命中
0011    } //一旦找到，随即终止
0012    return -1; //查找失败
0013 } //有多个命中元素时，不能保证返回秩最大者；失败时，简单地返回-1，而不能指示失败的位置