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:
- position of the smallest number just > (greater) a given number
- 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:
- 5 will give an iterator pointing to 6 located at index 1.
- 9 will give an iterator pointing to 10 located at index 5.
- 2 will give an iterator a.begin() i.e., element 5 located at index 0.
- 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
- 15 will give an iterator pointing to 15 located at index 5.
- 9 will give an iterator pointing to 9 located at index 2. (will give the leftmost occurrence in case of multiple data)
- 2 will give an iterator a.begin() i.e., element 5 located at index 0.
- 30 will give an iterator a.end() as there is no such element >= 30 in the list.