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 // 二分查找算法(版本B):在有序向量的区间[lo, hi)内查找元素e,0 <= lo < hi <= _size 0010 template <typename T> static Rank binSearch ( T* S, T const& e, Rank lo, Rank hi ) { 0011 while ( 1 < hi - lo ) { //每步迭代仅需做一次比较判断,有两个分支;成功查找不能提前终止 0012 Rank mi = ( lo + hi ) >> 1; //以中点为轴点(区间宽度的折半,等效于宽度之数值表示的右移) 0013 ( e < S[mi] ) ? hi = mi : lo = mi; //经比较后确定深入[lo, mi)或[mi, hi) 0014 } //出口时hi = lo + 1,查找区间仅含一个元素A[lo] 0015 return e < S[lo] ? lo - 1 : lo; //返回位置,总是不超过e的最大者 0016 } //有多个命中元素时,不能保证返回秩最大者;查找失败时,简单地返回-1,而不能指示失败的位置