Daily bit(e) of C++ | std::lower_bound, 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).
ncG1vNJzZmirmaK8r8DOrZ9nq6WXwLWtwqRlnKedZL1wsMCio7Jlkp7BpnnOn2ScZaOpsa271p6pmJqfqruledKtm66ooJq%2FoK7OrqWdZWGasw%3D%3D
Christie Applegate
Update: 2024-12-04