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 log2(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.