|
| |
|
| 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 functors 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 ForwardIterator.
-
LessThanComparable is a model of LessThanComparable.
-
The ordering on objects of type
LessThanComparable is a strict weak ordering, as defined in the LessThanComparable requirements.
-
ForwardIterator's value type is the same type as LessThanComparable.
For the second version:
-
ForwardIterator is a model of ForwardIterator.
-
StrictWeakOrdering is a model of StrictWeakOrdering.
-
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 functors 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
The number of comparisons is logarithmic: at most log(last - first) + 2. If ForwardIterator is a RandomAccessIterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last - first. [3]
Example
int main()
{
int A[] = { 1, 2, 3, 3, 3, 5, 8 };
const int N = sizeof(A) / sizeof(int);
for (int i = 1; i <= 10; ++i) {
cout << "Searching for " << i << ": "
<< (binary_search(A, A + N, i) ? "present" : "not present") << endl;
}
}
The output is:
Searching for 1: present
Searching for 2: present
Searching for 3: present
Searching for 4: not present
Searching for 5: present
Searching for 6: not present
Searching for 7: not present
Searching for 8: present
Searching for 9: not present
Searching for 10: not present
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 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 this is not necessarily the information you are interested in! Usually, if you're testing whether an element is present in a range, you'd like to know where it is (if it's present), or where it should be inserted (if it's not present). The functions lower_bound, upper_bound, and equal_range provide this information.
[3] This difference between RandomAccessIterator and ForwardIterator is simply because advance is constant time for RandomAccessIterator and linear time for ForwardIterator.
See also
lower_bound, upper_bound, equal_range
