binary_search [Sorting Algorithms]

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 , 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)
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 >
boost::range_const_iterator< I > ::type	binary_search (const I &range, const T &x, C c)
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 >
boost::range_const_iterator< I > ::type	binary_search (const I &range, 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 >
I	binary_search (I f, I l, const T &x)
template<typename I , typename T , typename C >
I	binary_search (I f, I l, const T &x, C c)

---

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

• STL documentation for binary_search
• lower_bound
• upper_bound
• equal_range

---

Function Documentation

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

Definition at line 101 of file binary_search.hpp.

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
	)

Definition at line 163 of file binary_search.hpp.

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
	)

Definition at line 152 of file binary_search.hpp.

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

Definition at line 139 of file binary_search.hpp.

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

Definition at line 133 of file binary_search.hpp.

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

Definition at line 127 of file binary_search.hpp.

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

Definition at line 121 of file binary_search.hpp.

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

Definition at line 117 of file binary_search.hpp.

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

Definition at line 110 of file binary_search.hpp.