0001 // 二分查找算法(版本A):在有序向量的区间[lo, hi)内查找元素e,0 <= lo <= hi <= _size 0002 template <typename T> static Rank binSearch ( T* S, T const& e, Rank lo, Rank hi ) { 0003 while ( lo < hi ) { //每步迭代可能要做两次比较判断,有三个分支 0004 Rank mi = ( lo + hi ) >> 1; //以中点为轴点(区间宽度的折半,等效于宽度之数值表示的右移) 0005 if ( e < S[mi] ) hi = mi; //深入前半段[lo, mi)继续查找 0006 else if ( S[mi] < e ) lo = mi + 1; //深入后半段(mi, hi)继续查找 0007 else return mi; //在mi处命中 0008 } //成功查找可以提前终止 0009 return -1; //查找失败 0010 } //有多个命中元素时,不能保证返回秩最大者;查找失败时,简单地返回-1,而不能指示失败的位置