内容来自 TsinghuaX: 30240184X 数据结构(2015秋) 课程的Vector一章，对有序向量的二分查找有三个版本
三个版本的函数原型是一致的，都是 Rank search(T const& e, Rank lo, Rank hi) const;
其中，Rank为向量元素的秩，在此被定义为int型，lo和hi分别是查找区间的左、右界桩。
若查找成功，则返回元素出现的秩；查找失败返回-1.
版本a和版本b在实现上的区别可用下图描述，其中+1,+2表示进入此分支要进行的比较次数（即 if 语句的层数）。
就像老师说的，两个版本都比对方的最坏情况好一点，比最好情况坏一点。
b的命中总在叶结点，而a可在中间结点命中（有点像B树和B+），因此a有一半的情况比b要快，但b比a稳定且比较次数少。
1 //版本a，中点命中直接返回（可在中间结点退出搜索），左右分支的比较次数不平衡（可用fibonacci查找优化），不稳定，失败返回-1 2 Rank search_a(T const& e, Rank lo, Rank hi) const{ 3 while (lo < hi) 4 { 5 Rank mi = (lo + hi) >> 1;//向下取整，因此lo=hi时,mi=lo 6 if (e < A[mi]) hi = mi;//进入左区间 7 else if (A[mi] < e) lo = mi + 1;//进入右区间 8 else return mi; 9 } 10 return -1; 11 } 12 13 //版本b，只能在区间长度收缩为1（抵达叶结点）时退出搜索，左右分支比较次数平衡，稳定，失败返回-1 14 Rank search_b(T const& e, Rank lo, Rank hi) const{ 15 while (1 < hi - lo){ 16 Rank mi = (lo + hi) >> 1; 17 e < A[i] ? hi = mi : lo = mi; 18 } 19 return A[lo] == e ? lo : -1; 20 }
版本c有更多语义上的规定，当查找成功时，若有多个元素与e相等，返回秩最大的那个；当查找失败时，返回应插入的位置，即最后一个小于等于e的元素的秩。
即对于成功或失败，都返回“不大于e的秩最大的元素的秩”
1 //版本c 2 Rank search_c(T const& e, Rank lo, Rank hi) const{ 3 while (lo < hi){ 4 Rank mi = (lo + hi) >> 1; 5 e < A[mi] ? hi = mi : lo = mi + 1; 6 } 7 return --lo; 8 }
可用下图描述版本c
