§ C++ lower_bound, upper_bound API

I never remember what precisely lower_bound returns, so this is me collecting this information in a way that makes sense to me. The API docs say

Returns an iterator pointing to the first element in the range [first,last)
which does not compare less than val.

• So lower_bound(first, last, bound) it finds the leftmost location l in [first..last) such that as[l] >= bound.
• See that it can be equal to the value bound.

In contrast, upper_bound says:

Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

• So upper_bound(first, last, bound) it finds the leftmost location l in [first..last) such that as[l] > bound.

§ Pictorially

If we have a range:

<<<<<<< ======= >>>>>>>>
        |     |
        L     R

• The < values are less than bound, = values are equal to bound, and > values are greater than bound, then lower_bound and upper_bound return iterators to represent the = range [L, R] in half-open form.
• So we will have [lower_bound, upper_bound) = [L, R]. This matches the C++ API where everything uses half-open intervals.

<<<<<<< ======= >>>>>>>>
        L     R |
        lower   upper

§ Traversals

• $[L, H]$: loop as for(auto it = lowerbound(l); it < upperbound(h); ++it) {}. This works since upperbound(h) will find first index > h, so we include all =h.
• $[L, H)$: loop as for(auto it = lowerbound(l); it <= lowerbound(h); ++it) {}. This works lowerbound(h) first first index >= h, so we don't include any =h.
• $(L, H]$: use for(auto it = upperbound(l); it <= upperbound(h); ++it) {}. upperbound(l) finds first index >l, so we ignore values =l.
• $(L, H)$: use for(auto it = upperbound(l); it < lowerbound(h); ++it) {}.

How to think about which one we want? This about it as lowerbound shifts iterators towards the left, and upperbound shifts iterators to right.

• For [L, we want to shift beginning leftwards, so lowerbound(L).
• For (L, we want to shift beginning rightwards, so upperbound(L).
• For H], we want to shift ending rightwards, so upperbound(H).
• For H), we want to shift ending leftwards, so lowerbound(H).

§ equal_range

• To unify the above description, one can simply use std::equal_range(fst, last, val) which returns the half-open interval [l, r) where the array has value val. This is equivalent to returning a pair of lower_bound, upper_bound.