C++ - 已排序的std :: vector中的元素索引

Question

我有一个std::vector我知道的是有序的.使用std::binary_search我可以在日志时间中查找元素是否在向量中.遗憾的是,std::binary_search如果成功,则不返回向量中元素的索引(或者如果它不知道如何访问它).std::find将给我一个元素的迭代器,但它没有使用向量排序的事实,因此它以线性时间而不是日志时间运行.我知道我可以轻松实现自己的二进制搜索算法,但我想知道是否有办法在标准中执行此操作.

Answer 1

您可以将std::lower_bound[O（log（N））和std::distance（O（1）用于随机访问迭代器）：

auto lower = std::lower_bound(v.begin(), v.end(), val);
// check that value has been found
const bool found = lower != v.end() && *lower == val;

然后，要么

auto idx = std::distance(v.begin(), lower);

或简单的算术：

auto idx = lower - v.begin();

Answer 2

您想使用lower_bound()函数.它通常有用,但它可以达到您想要的目的,这有点时髦.