二分查找是有序数组查找的常用算法。时间复杂度为 $\mathcal{O} (logn)$，无论是成功还是失败，其平均查找长度[1]都是 $\mathcal{O} (1.50 \cdot logn)$。
不存在：返回不大于e的最后一个元素
template <typename T>
Rank Vector<T>::search(T const &e, Rank lo, Rank hi) const {
while (lo < hi) {
Rank mi = (lo + hi) >> 1;
if (e < data_[mi]) {
hi = mi;
} else if (data_[mi] < e) {
lo = mi + 1;
} else {
return mi;
}
}
return -1;
}
-
查找长度是关键码的比较次数 ↩︎