Category: algorithms | Component type: function |
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);
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.
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
[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 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 Random Access Iterators and Forward Iterators is simply because advance is constant time for Random Access Iterators and linear time for Forward Iterators.