0001 template <typename T>
0002 Rank binSearch(T* S, const T& e, Rank lo, Rank hi) {
0003    while (lo < hi) { //每步迭代两次比较、三个分支
0004       Rank mi = (lo+hi)/2; //以中位数为轴点，区间宽度折半
0005       if (e < S[mi]) hi = mi; //深入前缀[lo,mi)继续查找
0006       else if (S[mi] < e) lo = mi+1; //深入后缀(mi,hi)继续查找
0007       else return mi; //命中，收工：有多个e时，未必能返回秩最大者
0008    } //出口时lo==hi
0009    return -1; //失败，但-1不能指示失败的位置
0010 } //版本A