c++ - 如何以最有效的方式在已排序的 C++ 向量中查找值？

Question

我看过find和binary_search，但 find 没有利用向量已排序的事实，并且 binary_search 只返回真或假，而不是它找到值的位置。有没有什么功能可以让我两全其美？

Answer 1

您可以使用 find 在 O(N) 时间内定位任何容器中的特定元素。使用向量，您可以进行随机访问并利用 std 算法的 lower_bound (log2(N))、upper_bound 或 equal_range 类。std::lower_bound将为您做到这一点。它位于 binary_search 顶部的等效行为部分。但是，binary_search 的实用性仅限于是和否的答案（可能在未来的 C++ 版本中需要改进命名；binary_in()）。

Answer 2

有一种方法 ，std::equal_range它将为您提供一对包含持有所需值的子集的下限和上限。如果这对中的这两个项目相同，则您要查找的值不存在。

Answer 3

template<class T, class U>
bool contains(const std::vector<T>& container, const U& v)
{
    auto it = std::lower_bound(
        container.begin(),
        container.end(),
        v,
        [](const T& l, const U& r){ return l < r; });
    return it != container.end() && *it == v;
}