# Binary Search

The fast search which has a search time of O(log n) has been predefined in C++.

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`

you get an iterator for the first element, being no smaller than the given value. With `std::upper_bound`

you 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, you need on average **log _{2}(n)** comparisons for the search. The binary search requires that you use the same comparison criterion that you used for sorting the container. Per default the comparison criterion is

`std::less`

, but you can adjust it. Your sorting criterion has to obey the strict weak ordering. If not, the program is undefined.If you have an unordered associative container, the methods of the unordered associative container are in general faster.

Searches the element `val`

in the range:

Get hands-on with 1000+ tech skills courses.