Binary Search

The binary search algorithms use the fact that the ranges are already sorted. To search for an element, use std::binary_search. With std::lower_bound, we get an iterator for the first element, not smaller than the given value. With std::upper_bound, we get an iterator back for the first element which is bigger than the given value. std:::equal_range combines both algorithms.

If the container has n elements, we need on average log₂(n) comparisons for the search. The binary search requires that we use the same comparison criterion that you used for sorting the container. By default, the comparison criterion is std::less, but we can adjust it. Our sorting criterion has to obey strict weak ordering. If not, the result is undefined.

If we have an unordered associative container, the methods of the unordered associative container are generally faster.

std::binary_search: Searches for the element val in the range.