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

--

## 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