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`

.