'How to find a value in a sorted C++ vector in the most efficient way?

I have looked at find and binary_search, but find doesn't take advantage of the fact that the vector is sorted, and binary_search only returns a true or false, not where it found the value. Is there any function that can give me the best of both worlds?

c++sortingsearchvectorfind


Solution 1:[1]

There is a method, std::equal_range, which will give you a pair containing the lower and upper bound of the subset holding the desired value. If both of those items in the pair are identical, then the value you were looking for doesn't exist.

Solution 2:[2]

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;
}

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2 Gabriel Schreiber

Related Questions