Brief overview:-

The functions upper_bound() and lower_bound() functions are useful when we have data stored in a non-decreasingly sorted format and in a given range in the data structure we want to find out:

1. position of the smallest number just > (greater) a given number
2. position of the smallest number >= (greater than or equal to) a given number

we can use these 2 functions.

Lets take an example data and understand:- vector<int> a = {5,6,9,9,10,15,19,25};

upper_bound() :-

• returns an iterator pointing to the element just greater than the given number
• upper_bound of:

1. 5 will give an iterator pointing to 6 located at index 1.
2. 9 will give an iterator pointing to 10 located at index 5.
3. 2 will give an iterator a.begin() i.e., element 5 located at index 0.
4. 25 will give an iterator a.end() as there is no such element > 25 in the list.

lower_bound() :-

• returns an iterator pointing to the element greater than or equal to the given number
• lower_bound of

1. 15 will give an iterator pointing to 15 located at index 5.
2. 9 will give an iterator pointing to 9 located at index 2. (will give the leftmost occurrence in case of multiple data)
3. 2 will give an iterator a.begin() i.e., element 5 located at index 0.
4. 30 will give an iterator a.end() as there is no such element >= 30 in the list.