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 Answers
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()).
-
4Keep 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()
. 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 usestd::equal_range
,std::lower_bound
should be preferred for binary searches. Jul 4, 2017 at 11:42
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.
-
1If 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– QBziZJul 7, 2016 at 14:38
-
This is not a good answer. What if I'll search for the value of
6
, but myset
only contains5
and7
. This pair will be returned (instead ofset.end()
, and it won't be a failed binary search. There would be no way other way of knowing if it really found5
or something inbetween than looking at the value. And for this reasonstd::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?– NickAug 1, 2017 at 14:33
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;
}
-
2it 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 Jul 16, 2020 at 14:12
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";
binary_search
page you referred to. The "See Also" section.