排序向量上std :: lower_bound的时间复杂度

Question

我正在研究std::upper_bound从http://www.cplusplus.com/reference/algorithm/upper_bound/ 和我遇到的事实，这可能在上线时间来运行非随机访问迭代器。

我需要将此用于已排序的向量。现在，我不知道什么是非随机访问迭代器，以及它是否将在排序后的向量上以对数时间运行。

谁能为我清除此问题。

Answer 1

§23.3.6.1 [vector.overview] / p1：

向量是支持随机访问迭代器的序列容器。

一个随机访问迭代器是一个能够计算一定时间内的任意元素的偏移量，而不需要遍历从一个地方到另一个地方（会导致线性复杂的）。

std::lower_bound本身提供了二进制搜索算法的通用实现，它并不在乎使用什么迭代器来指示范围（它仅要求迭代器至少为正向类别）。它使用帮助函数std::advance来迭代限制其二进制搜索中的范围。用std::vector<T>::iterator这是一个随机接入类别的，std::lower_bound与关于以上元件所需迭代的，因为它可通过在一半在恒定时间每一步划分范围步数对数时间复杂度运行。

第25.4.3节[alg.binary.search] / p1：

本节中的所有算法都是二进制搜索的版本，并假设相对于通过将搜索键绑定到隐式或显式比较函数的自变量形成的表达式，对要搜索的序列进行了分区。它们在非随机访问迭代器上工作，可最大程度地减少比较次数，这对于所有类型的迭代器都是对数的。它们特别适合于随机访问迭代器，因为这些算法在数据结构中进行的步数为对数。对于非随机访问迭代器，它们执行线性数量的步骤。