Searching for 2
First position where 2 could be inserted: 1
Last position where 2 could be inserted: 2
*result.first = 2
*result.second = 3
Searching for 3
First position where 3 could be inserted: 2
Last position where 3 could be inserted: 5
*result.first = 3
*result.second = 5
Searching for 4
First position where 4 could be inserted: 5
Last position where 4 could be inserted: 5
*result.first = 5
*result.second = 5
Notes [1] Note that you may use an ordering that is a strict weak ordering but not a total ordering; that is, there might be values x and y such that x < y, x > y, and x == y are all false. (See the LessThan Comparable requirements for a more complete discussion.) Finding value in the range [first, last), then, doesn't mean finding an element that is equal to value but rather one that is equivalent to value: one that is neither greater than nor less than value. If you're using a total ordering, however (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.
[2] Note that equal_range may return an empty range; that is, it may return a pair both of whose elements are the same iterator. Equal_range returns an empty range if and only if the range [first, last) contains no elements equivalent to value. In this case it follows that there is only one position where value could be inserted without violating the range's ordering, so the return value is a pair both of whose elements are iterators that point to that position.
[3] This difference between Random Access Iterators and Forward Iterators is simply because advance is constant time for Random Access Iterators and linear time for Forward Iterators.
See also lower_bound, upper_bound, binary_search
Category: algorithms
Component type: function
Prototype Binary_search is an overloaded name; there are actually two binary_search functions.
template <class ForwardIterator, class LessThanComparable>
bool binary_search(ForwardIterator first, ForwardIterator last, const LessThanComparable& value);
template <class ForwardIterator, class T, class StrictWeakOrdering>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);
Description Binary_search is a version of binary search: it attempts to find the element value in an ordered range [first, last) It returns true if an element that is equivalent to [1] value is present in [first, last) and false if no such element exists. [2] The first version of binary_search uses operator< for comparison, and the second uses the function object comp.
Specifically, the first version returns true if and only if there exists an iterator i in [first, last) such that *i < value and value < *i are both false. The second version returns true if and only if there exists an iterator i in [first, last) such that comp(*i, value) and comp(value, *i) are both false.
Definition Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
Requirements on types For the first version:
• ForwardIterator is a model of Forward Iterator.
• LessThanComparable is a model of LessThan Comparable.
• The ordering on objects of type LessThanComparable is a strict weak ordering, as defined in the LessThan Comparable requirements.
• ForwardIterator's value type is the same type as LessThanComparable.
For the second version:
• ForwardIterator is a model of Forward Iterator.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• ForwardIterator's value type is the same type as T.
• ForwardIterator's value type is convertible to StrictWeakOrdering's argument type.
Preconditions For the first version:
• [first, last) is a valid range.
• [first, last) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first, last) such that i precedes j, *j < *i is false.
For the second version:
• [first, last) is a valid range.
• [first, last) is ordered in ascending order according to the function object comp. That is, for every pair of iterators i and j in [first, last) such that i precedes j, comp(*j, *i) is false.
Complexity 
