Demystifying S.T.L. functions upper_bound() & lower_bound();

catchy picture to gather views.

There are a lot of articles/documentations on the internet that start with the defintion of upper_bound() & lower_bound(), but I don’t want to indulge in all that bare talking. We’ll come to the defintions, but not right now.

Lets dive directly into the examples :

let’s consider a sorted array : 10, 20, 30, 40, 50

and now let’s find upper_bound() for the following values :

val : 30, upper_bound : 40, index = 3

val : 40, upper_bound : 50, index = 4

… can you see a pattern in this? if not let me throw some more values,

val : 45, upper_bound : 50, index = 4

val : 15, upper_bound : 20, index = 1

val : 18, upper_bound : 20, index = 1

val : 10, upper_bound : 20, index = 1

well, upper_bound() returns an element from the array that is just greater than val.

Let’s talk about an exception, what if our val is : 60, or 65, or anything greater than the last element of the given array?

val : 60, upper_bound returns : end of the array.

cpp program

output

and what if, we have too many duplicate just greater than elements than our val,

val : 40, array : 10, 20, 30, 40, 50, 50, 50, 50, 60

upper_bound : 50, of index : 4(0 based indexing).

val : 40

upper_bound for val = 40

So, upper_bound() returns an iterator pointing to the first element in the range [first, last) that is greater than value, or end of the array if no such element is found.

Now, let’s talk about lower_bound(), and once again let’s dive directly into the examples,

let’s consider a sorted array : 10, 20, 30, 40, 50

val : 30, lower_bound : 30, index : 2

val : 35, lower_bound : 40, index : 3

val : 10, lower_bound : 10, index : 0

val : 20, lower_bound : 20, index : 1

val : 25, lower_bound : 30, index : 2

…did you notice some caveat?

well, lower_bound returns an element that is just not less than the given val, in simple words, if val is found it returns val otherwise it returns the element just greater than val.

Let’s talk about an exception, what if the element we’re looking for is absent plus the element just greater than is also not in the array,

then lower_bound returns the end of the array.

val : 60, lower_bound : end of the array.

dummy cpp program

output

What about the case when there are multiple occurrences of val??

val : 30, array : 10, 20, 30, 30, 30, 30, 40, 50

lower_bound : 30, at index : 2

dummy cpp program

output

Viva-La-Vida

Here’s some practice questions for you,

find lower_bound & upper_bound for the array : 10, 20, 30,40,50,60

values : 10, 20, 45, 50, 60, 70