|
Functions |
template<typename I , typename T , typename C , typename P > |
I | binary_search (I f, I l, const T &x, C c, P p) |
template<typename I , typename T , typename C > |
I | binary_search (I f, I l, const T &x, C c) |
template<typename I , typename T > |
I | binary_search (I f, I l, const T &x) |
template<typename I , typename T > |
boost::range_iterator< I >::type | binary_search (I &range, const T &x) |
template<typename I , typename T > |
boost::range_const_iterator< I >
::type | binary_search (const I &range, const T &x) |
template<typename I , typename T , typename C > |
boost::range_iterator< I >::type | binary_search (I &range, const T &x, C c) |
template<typename I , typename T , typename C > |
boost::range_const_iterator< I >
::type | binary_search (const I &range, const T &x, C c) |
template<typename I , typename T , typename C , typename P > |
boost::lazy_disable_if
< boost::is_same< I, T >
, boost::range_iterator< I >
>::type | binary_search (I &r, const T &x, C c, P p) |
template<typename I , typename T , typename C , typename P > |
boost::lazy_disable_if
< boost::is_same< I, T >
, boost::range_const_iterator
< I > >::type | binary_search (const I &r, const T &x, C c, P p) |
Detailed Description
binary_search() is a version of binary search: it attempts to find the element value in an ordered range [f, l) . It returns an iterator to the first instance that is equivalent to [1] x if such a value s present and l if no such elment exists. binary_search() takes an optional comparision function and uses adobe::less() if not provided.
- Requirements:
-
- Precondition:
[f, l) is a valid range.
[f, l) is ordered in ascending order according to c . That is, for every pair of iterators i and j in [f, l) such that i precedes j , c(*j, *i) is false.
- Complexity Guarantees:
- The number of comparisons is logarithmic: at most
log(l - f) + 2 . If I is a RandomAccessIterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last - first. [2]
- 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 LessThanComparable requirements for a more complete discussion.) Finding
x in the range [f, l) , then, doesn't mean finding an element that is equal to x but rather one that is equivalent to x: one that is neither greater than nor less than x . 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] This difference between RandomAccessIterator and ForwardIterator is simply because advance is constant time for RandomAccessIterator and linear time for ForwardIterator.
- Note:
binary_search() differs from binary_search in that it returns an iterator to the first element rather than simply a bool . This is commonly a more useful function. binary_search is similar to lower_bound except it returns l if no element matching x exists.
- See also:
-
Function Documentation
I adobe::binary_search |
( |
I |
f, |
|
|
I |
l, |
|
|
const T & |
x, |
|
|
C |
c, |
|
|
P |
p |
|
) |
| |
I adobe::binary_search |
( |
I |
f, |
|
|
I |
l, |
|
|
const T & |
x, |
|
|
C |
c |
|
) |
| |
I adobe::binary_search |
( |
I |
f, |
|
|
I |
l, |
|
|
const T & |
x |
|
) |
| |
boost::range_iterator<I>::type adobe::binary_search |
( |
I & |
range, |
|
|
const T & |
x |
|
) |
| |
boost::range_const_iterator<I>::type adobe::binary_search |
( |
const I & |
range, |
|
|
const T & |
x |
|
) |
| |
boost::range_iterator<I>::type adobe::binary_search |
( |
I & |
range, |
|
|
const T & |
x, |
|
|
C |
c |
|
) |
| |
boost::range_const_iterator<I>::type adobe::binary_search |
( |
const I & |
range, |
|
|
const T & |
x, |
|
|
C |
c |
|
) |
| |
boost::lazy_disable_if<boost::is_same<I, T>, boost::range_iterator<I> >::type adobe::binary_search |
( |
I & |
r, |
|
|
const T & |
x, |
|
|
C |
c, |
|
|
P |
p |
|
) |
| |
boost::lazy_disable_if<boost::is_same<I, T>, boost::range_const_iterator<I> >::type adobe::binary_search |
( |
const I & |
r, |
|
|
const T & |
x, |
|
|
C |
c, |
|
|
P |
p |
|
) |
| |
|