binary_search

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< std::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< std::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

• I is a model of ForwardIterator.
• C is a model of LessThanComparable.
• value_type(I) == argument_type(C)

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 Guarantee(s)

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 std::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

• STL documentation for binary_search
• lower_bound
• upper_bound
• equal_range

Function Documentation

binary_search() [1/9]

template<typename I, typename T, typename C, typename P>

I binary_search	(	I	f,
		I	l,
		const T &	x,
		C	c,
		P	p )

Definition at line 104 of file binary_search.hpp.

binary_search() [2/9]

template<typename I, typename T, typename C>

I binary_search	(	I	f,
		I	l,
		const T &	x,
		C	c )

Definition at line 113 of file binary_search.hpp.

binary_search() [3/9]

template<typename I, typename T>

I binary_search	(	I	f,
		I	l,
		const T &	x )

Definition at line 120 of file binary_search.hpp.

binary_search() [4/9]

template<typename I, typename T>

boost::range_iterator< I >::type binary_search	(	I &	range,
		const T &	x )

Definition at line 125 of file binary_search.hpp.

binary_search() [5/9]

template<typename I, typename T>

boost::range_const_iterator< I >::type binary_search	(	const I &	range,
		const T &	x )

Definition at line 130 of file binary_search.hpp.

binary_search() [6/9]

template<typename I, typename T, typename C>

boost::range_iterator< I >::type binary_search	(	I &	range,
		const T &	x,
		C	c )

Definition at line 135 of file binary_search.hpp.

binary_search() [7/9]

template<typename I, typename T, typename C>

boost::range_const_iterator< I >::type binary_search	(	const I &	range,
		const T &	x,
		C	c )

Definition at line 140 of file binary_search.hpp.

binary_search() [8/9]

template<typename I, typename T, typename C, typename P>

boost::lazy_disable_if< std::is_same< I, T >, boost::range_iterator< I > >::type binary_search	(	I &	r,
		const T &	x,
		C	c,
		P	p )

Definition at line 152 of file binary_search.hpp.

binary_search() [9/9]

template<typename I, typename T, typename C, typename P>

boost::lazy_disable_if< std::is_same< I, T >, boost::range_const_iterator< I > >::type binary_search	(	const I &	r,
		const T &	x,
		C	c,
		P	p )

Definition at line 163 of file binary_search.hpp.