I just recently started to understand why
lower_bound is called
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
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
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
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, and
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
When I initially came across these two functions, I often thought of the math
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
So the answer to this question is: lower_bound can be seen as a lower bound of
== val part, and upper_bound can be seen as an upper bound of the
part. Now it makes sense, even in a mathematical sense.