I just recently started to understand why lower_bound is called lower_bound and upper_bound is called upper_bound. I will explain this in this article.

First, let’s do a quick recap of the definitions of these two functions. The function lower_bound is defined as “Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val” (See API reference). The function upper_bound is defined as “Returns an iterator pointing to the first element in the range [first,last) which compares greater than val” (See API reference).

An illustration of lower_bound and
upper_bound

In essence, lower_bound and upper_bound are both doing binary search. But why do we need two functions for one algorithm?

The reason is simple: we have two boundaries for a given value and a sorted array, as illustrated in the picture.

Formally, given a sorted array, and a value val you want to search for, the array typically can be partitioned into 3 parts: < val, == val, and > val, as illustrated in the picture above.

For binary search, the most important positions are the two boundaries, and from the picture, it’s obvious that one bound is lower, while the other is upper. So I think that’s why they’re named as lower_bound and upper_bound.

When I initially came across these two functions, I often thought of the math concept lower bound and upper bound (see wiki). Then I had a question in mind: the returned iterator points to a lower bound? A lower bound of what?

So the answer to this question is: lower_bound can be seen as a lower bound of the == val part, and upper_bound can be seen as an upper bound of the == val part. Now it makes sense, even in a mathematical sense.