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

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.

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).

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.

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

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Abhishek Gururani

Abhishek Gururani

31 Followers

I write articles on Android Development, and problem solving.