Daily bit(e) of C++ | std::lower_bound, std::upper_bound
Daily bit(e) of C++ ♻️123, The two binary search algorithms: std::lower_bound and std::upper_bound.
The std::lower_bound and std::upper_bound are arguably the two most practically useful algorithms in the standard library.
Both algorithms are binary searches, operating in O(logn) on sorted ranges.
The std::lower_bound returns an iterator to the first element not ordered before the provided value and std::upper_bound to the first element ordered after the provided value.
Note that the number of comparisons is still O(logn) on non-random-access ranges. However, the number of iterator increments is O(n).
