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

Question

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?

Bahamas

Look at the bottom of the binary_search page you referred to. The "See Also" section. – Florindaflorine

Perhaps you may want to take a look at this: https://mcmap.net/q/324330/-binary-search-c-stl – Jenifferjenilee

@elimirks Your request could be phrased more politely. If you don't have time to actually describe what you're after, consider not commenting. Welcome to Stackoverflow – Jaxartes

There is no additional context required to resolve this problem. – Hexagon

Answer 1

You can use find to locate a particular element in any container in time O(N). With vector you can do random access and take advantage of the lower_bound (log2(N)), upper_bound, or equal_range class of std algorithms. std::lower_bound will do that for you. It's in the equivalent-behavior section at the top for binary_search. However, the utility of binary_search is limited to yes and no answers (maybe the naming needs to be improved in the future version of C++; binary_in()).

Casto

Keep in mind that gives you the element which is greater than or equal to val, so you still have to check it to see if it exists. But that may well be more efficient to do that two-step rather than use std::equal_range(). – Ribbentrop

std::equal_range is not sufficient for checking existence too, also it has a worse performance. Unless you have a good reason to use std::equal_range, std::lower_bound should be preferred for binary searches. – File

Answer 2

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.

Ribbentrop

If std::distance( res.first, res.second ) == 1 then there is exactly one item found. If first and second would be identical then the distance would be 0, but that is not the case. See "Return value" in en.cppreference.com/w/cpp/algorithm/equal_range – Saccharide

This is not a good answer. What if I'll search for the value of 6, but my set only contains 5 and 7. This pair will be returned (instead of set.end(), and it won't be a failed binary search. There would be no way other way of knowing if it really found 5 or something inbetween than looking at the value. And for this reason std::lower_bound should be sufficient. – File

but it still do 2 * log(N) instead simple log(N) for home made binary search? Am I correct? – Risotto

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

Midwifery

it doesn't answer to the OP question (which is asking for the index in the vector where the value was found) and it is doing what en.cppreference.com/w/cpp/algorithm/binary_search is already doing – Bloom

Answer 4

You can use the following method to check if an element 'x' is present or not in a sorted vector 'vec' and print its index in one go and in O(log n) time complexity.

int ind = lower_bound(vec.begin(), vec.end(), x) - vec.begin();

if(ind != vec.size() && vec[ind] == x)
    cout << "Found at: " << ind;  
else
    cout << "Not found";

Tungusic