std::lower_bound and std::upper_bound STL functions in C++

Introduction:    

For a sorted sequence

std::lower_bound and std::upper_bound are two very powerful functions in C++ STL, which can save you from writing a long code of binary search(specially in competitive programming).

Basically these functions are used to find the lower bound or upper bound for a given value in a sorted sequence of elements (vector, arrays, sets, maps etc.)

Definition:

lower_bound for a value 'val' finds the location of the first element which is just greater than or equal to val.

And

upper_bound function for a value 'val' unlike lower_bound just finds the location of the first element which is just greater than val.

Syntaxes:

std::lower_bound ( iterator start, iterator last, const val ) ;

std::upper_bound ( iterator start, iterator last, const val ) ;

Time Complexity:

In case of vectors, arrays it is O(log(n))

In case of sets, maps it is O(n)

To get results in O(logn) in case of sets and maps we should use map.lower_bound(const val) instead of lower_bound(map.begin(), map.end(), const val) and same for upper_bound also.

For example:

std::vector<int> v = {1, 2, 3, 4, 5, 5, 5, 6, 8, 9};    // 10 elements

std::lower_bound(v.begin(), v.end(), 5);    

//above function returns an iterator to index 4 i.e. v[4] = 5

std::upper_bound(v.begin(), v.end(), 5);    

//above function returns an iterator to index 7 i.e. v[7] = 6, just > 5

Note: if we are trying to find bound for an element which is greater than the last element(maximum element) then neither std::lower_bound will find that or greater than that nor std::upper_bound will find just greater than that element because that element is out of range of the our given sequence.

In this case both will return location just next to last element i.e. iterator v.end()

Thanks....