the_mandrill - 9 months ago 51

C++ Question

Is there a function in that uses binary search, like

`lower_bound`

`lower_bound`

Finds the position of thefirstelement in an ordered range that has a valuegreater than or equivalent toa specified value, where the ordering criterion may be specified by a binary predicate.

and

`upper_bound`

Finds the position of thefirstelement in an ordered range that has a value that isgreater thana specified value, where the ordering criterion may be specified by a binary predicate.

Specifically, I have a container of time ordered events and for a given time I want to find the last item that came before or at that point. Can I achieve this with some combination of upper/lower bound, reverse iterators and using

`std::greater`

`std::greater_equal`

EDIT:

A tweak was needed to user763305's suggestion to cope with if you ask for a point before the start of the array:

`iterator it=upper_bound(begin(), end(), val, LessThanFunction());`

if (it!=begin()) {

it--; // not at end of array so rewind to previous item

} else {

it=end(); // no items before this point, so return end()

}

return it;

Answer Source

In a sorted container, the last element that is less than or equivalent to `x`

, is the element before the first element that is greater than `x`

.

Thus you can call `std::upper_bound`

, and decrement the returned iterator once.
(Before decrementing, you must of course check that it is not the begin iterator; if it is, then there are no elements that are less than or equivalent to `x`

.)