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

Question

我有一个我知道已排序的 std::vector。使用 std::binary_search 我可以在日志时间内找到一个元素是否在 vector 中。不幸的是，如果成功，std::binary_search 不会返回 vector 中元素的索引(或者如果成功了，我不知道如何访问它)。 std::find 会给我一个元素的迭代器，但它没有使用 vector 已排序的事实，因此它以线性时间而不是对数时间运行。我知道我可以轻而易举地实现我自己的二进制搜索算法，但我想知道在标准中是否有一种方法可以做到这一点。

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();