0001 /****************************************************************************************** 0002 * Data Structures in C++ 0003 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3 0004 * Junhui DENG, deng@tsinghua.edu.cn 0005 * Computer Science & Technology, Tsinghua University 0006 * Copyright (c) 2003-2019. All rights reserved. 0007 ******************************************************************************************/ 0008 0009 #include "fibonacci/Fib.h" //引入Fib数列类 0010 // Fibonacci查找算法(版本A):在有序向量的区间[lo, hi)内查找元素e,0 <= lo <= hi <= _size 0011 template <typename T> static Rank fibSearch ( T* S, T const& e, Rank lo, Rank hi ) { 0012 //用O(log_phi(n = hi - lo)时间创建Fib数列 0013 for ( Fib fib ( hi - lo ); lo < hi; ) { //Fib数列制表备查;此后每步迭代仅一次比较、两个分支 0014 while ( hi - lo < fib.get() ) fib.prev(); //自后向前顺序查找(分摊O(1)) 0015 Rank mi = lo + fib.get() - 1; //确定形如Fib(k) - 1的轴点 0016 if ( e < S[mi] ) hi = mi; //深入前半段[lo, mi)继续查找 0017 else if ( S[mi] < e ) lo = mi + 1; //深入后半段(mi, hi)继续查找 0018 else return mi; //在mi处命中 0019 } //成功查找可以提前终止 0020 return -1; //查找失败 0021 } //有多个命中元素时,不能保证返回秩最大者;失败时,简单地返回-1,而不能指示失败的位置