A.2.3. Binary Search Algorithms

These algorithms require forward iterators but are optimized so that they execute much more quickly if they are called with random-access iterators. Technically speaking, regardless of the iterator type, these algorithms execute a logarithmic number of comparisons. However, when used with forward iterators, they must make a linear number of iterator operations to move among the elements in the sequence.

These algorithms require that the elements in the input sequence are already in order. These algorithms behave similarly to the associative container members of the same name (§ 11.3.5, p. 438). The equal_range, lower_bound, and upper_bound algorithms return iterators that refer to positions in the sequence at which the given element can be inserted while still preserving the sequence’s ordering. If the element is larger than any other in the sequence, then the iterator that is returned might be the off-the-end iterator.

Each algorithm provides two versions: The first uses the element type’s less-than operator (<) to test elements; the second uses the given comparison operation. In the following algorithms, “x is less than y” means x < y or that comp(x, y) succeeds.

lower_bound(beg, end, val)
lower_bound(beg, end, val, comp)

Returns an iterator denoting the first element such that val is not less than that element, or end if no such element exists.

upper_bound(beg, end, val)
upper_bound(beg, end, val, comp)

Returns an iterator denoting the first element such that is val is less than that element, or end if no such element exists.

equal_range(beg, end, val)
equal_range(beg, end, val, comp)

Returns a pair (§ 11.2.3, p. 426) in which the first member is the iterator that would be returned by lower_bound, and second is the iterator upper_bound would return.

binary_search(beg, end, val)
binary_search(beg, end, val, comp)

Returns a bool indicating whether the sequence contains an element that is equal to val. Two values x and y are considered equal if x is not less than y and y is not less than x.