Graphical lower_bound & upper_bound

Official explanation of the two algorithms

lower_boundupper_bound

template< class ForwardIt, class T >ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

lower_bound is used to find the position of the first not less thanvalue in the ascending sequence, that is, to find the first>=values position.

template< class ForwardIt, class T >ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

upper_bound is used to find the first position in the ascending sequence that is greater than value.

Take it literally, with a little twist, let's look at two examples.

• Element exists in list

For sequence 1 2 2 3 3 4 4 5 5 6 6 7

We make lower_bound and upper_bound calls for value=3.

Because lower_bound requires the first >=, the position marked by [ in the figure is the target position

Because upper_bound requires the first>, the position marked with ) in the figure is the target position.

• Element does not exist in list

 

For sequence 1 3 3 6 6 9 9

We make lower_bound and upper_bound calls for value=4.

Because lower_bound requires the first >=, the position marked by [ in the figure is the target position

Because upper_bound requires the first>, the position marked with ) in the figure is the target position.

It can be seen from this that if the return value of lower_bound is equal to value, it means that value exists in the list, otherwise it does not exist.This is also a way to find an element in a list.

In this way, the names of lower_bound and upper_bound are easy to understand, "lower boundary and upper boundary", the lower boundary is a closed interval, and the upper boundary is an open interval, forming a left-closed and right-open interval [ )

p>

This design is consistent with the left-closed and right-open principle that STL iterators follow. All begin includes the target element, so the end does not include the target element.

We know that there is also a commonly used search function find in stl, which can be used to find elements. What is the difference between the two functions?

ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );InputIt find( InputIt first, InputIt last, const T& value );

Similarities: Both accept head and tail iterators and target elements.

Differences:

1. find does not require elements to be in order, lower_bound requires order.
2. find uses == to compare elements, and lower_bound uses < to compare elements.This is why lower_bound requires elements to be sorted.
3. find is linear search, lower_bound is binary search.

It can be seen that find is more general, while lower_bound is more efficient to search in ordered sequences.