If i have say 2 vectors, one in increasing order, and other decreasing
vector<int> inc{1,2,3,4,6,7}, dec{7,6,4,3,2,1};
Then do these 2 always give the same result…or is there any difference in how they work:-
lower_bound(inc.rbegin(), inc.rend(), some_number, greater<int>()) // #1
and
lower_bound(dec.begin(), dec.end(), some_number, greater<int>()) // #2
I feel they are the same but during a recent content on Codeforces, one got accepted while the other didn’t.
SHUBHAM KUMAR is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
6
From the algorithm’s, std::lower_bounds‘s, perspective, there is no differance other than the iterator type (one is a reverse iterator and the other one is not), but it doesn’t care about that.
It will perform the same algorithmic steps in both cases and return an iterator pointing at an element that carries the same value in both cases – or the end()/rend() iterator.
One minor difference could be in speed. I’d expect the version using reverse iterators to be a tad slower, but I haven’t measured.
So, other than the difference in the returned iterator type and possibly one being slower than the other, you will get the same value out of both versions.