有序向量的查找

查找

• 接口：tempalte static Rank search(T* a,T const& e, Rank lo, Rank hi)
• 语义规定：在有序向量的区间[lo, hi)内，确定不大于e的最后一个节点的秩
• 复杂度：若采用最朴素的二分策略，那么每次都将问题规模缩小一半左右，这样经过至多\(log_2(hi-lo)\)次迭代，复杂度不超过\(O(logn)\)，而改进基本上是线性因子。
• 查找长度：查找算法执行元素大小比较操作的次数

二分查找

语义规定：在有序向量的区间[lo, hi)内，返回e的秩，若有多个相同值则返回最大的秩，若查询失败则返回-1

原理：每次取lo与hi的终点，不停调整区间，经过至多两次比较可以完成一次迭代。
直到最后lo>=hi时(其实就是lo=hi)，此时的区间宽度为0，表示查询失败了。

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

查询长度分析：
为了评定各个查询的细微差距，我们考察查询长度，同样有最好最坏和平均。
这里我们依旧考察平均查询长度:\(C_{average}(k)\)
设在长度为\(n=2^k-1\)的有序向量中进行查询
1、成功查询长度

递推基：
\(C_{average}(k)=C(1)=2\)
递推分析：对于成功查询，总共有三种情况
1.经过1次比较，问题转化为2^{k-1}-1的新问题;
2.经过2次比较，问题转化为2^{k-1}-1的新问题;
3.经过2次比较，在mid处命中，查询成功.
那么则有递推公式

令

则有

于是

进而得到

n趋于无穷时忽略末尾收敛的无穷小量平均查找长度为：

Fibonacci查找

二分查找·改

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

二分查找·改二

template <typename T> static Rank binSearch ( T* S, T const& e, Rank lo, Rank hi ) {
   while ( lo < hi ) { //每步迭代仅需做一次比较判断，有两个分支
      Rank mi = ( lo + hi ) >> 1; //以中点为轴点（区间宽度的折半，等效于宽度之数值表示的右移）
      ( e < S[mi] ) ? hi = mi : lo = mi + 1; //经比较后确定深入[lo, mi)或(mi, hi)
   } //成功查找不能提前终止
   return lo - 1; //循环结束时，lo为大于e的元素的最小秩，故lo - 1即不大于e的元素的最大秩
} //有多个命中元素时，返回秩最大者；查找失败时，能够返回失败的位置