60

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?

4
  • 1
    Look at the bottom of the binary_search page you referred to. The "See Also" section. Sep 25, 2013 at 1:12
  • Perhaps you may want to take a look at this: stackoverflow.com/questions/4284049/binary-search-c-stl
    – rcs
    Sep 25, 2013 at 1:13
  • 7
    @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
    – sehe
    Sep 25, 2013 at 1:44
  • 7
    There is no additional context required to resolve this problem.
    – Puppy
    Sep 25, 2013 at 1:46

4 Answers 4

57

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

2
  • 4
    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().
    – paxdiablo
    Sep 25, 2013 at 1:35
  • 1
    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. Jul 4, 2017 at 11:42
21

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.

3
  • 1
    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
    – QBziZ
    Jul 7, 2016 at 14:38
  • 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. Jul 4, 2017 at 11:34
  • but it still do 2 * log(N) instead simple log(N) for home made binary search? Am I correct?
    – Nick
    Aug 1, 2017 at 14:33
8
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;
}
1
0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.