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,而不能指示失败的位置