upper_bound in C++

std::upper_bound()

The upper_bound C++ is a function that is used to find an iteration referring to the first element from a provided specific range. The range is defined as [first, last]. This function returns the value after the comparison from a parameter namely val. Upper_bound() C++ is a standard library function that is defined in the header file of the C++ program. If there is no value found compared to the parameter val from the given range, then the function returns an iteration whose value is "end value + 1". This function works internally based on a binary search algorithm that helps the program find the defined iteration in the val and range.

Syntax

There are two types of the syntax of the upper_bound() C++ function which are as follows:

• Syntax 1:

• Syntax 2:

Parameters

The parameters of the upper_bound() C++ function is as follows:

• first: It is the forward iteration point that is used to define the first element of the range that will be defined as the searching range of the function.
• last: It is a forward iteration that represents the last element of the searching range of the function.
• val: This parameter is the value of the upper bound that needs to be searched in the given range of the upper_bound C++ function.
• comp: This is an optional parameter of the upper_bound() C++ function. It is used to provide a customized range for the function. By following the strict weak ordering of the elements, it returns true and false on the basis or order of the elements.

Return Value

The return value of the upper_bound() C++ function is as follows:

• Return value: It returns an iteration that refers to the first element from the provided range. This value is greater than val otherwise the function returns the last element from the range if no such val is found.

Exceptions

The exception of the upper_bound() C++ function is as follows:

• The upper_bound() C++ function will throw an error if the element comparison of the function will throw an error.
• If you give any invalid parameter in this function, it will affect the functioning of the function, causing undefined behavior.

Examples

Now, let us see some examples of upper_bound() C++ to understand how this function works.

Example 1. Simple use of upper_bound() C++

• Output:

Example 2. Upper_bound() C++ with Arrays

• Output:

Complexity

The complexity of the upper_bound() C ++ function is as follows:

• The complexity of this function is the distance between the first and last elements given in the range. So it will be like (at most log2(last – first) + O(1) comparisons).
• On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

Important Points to Remember

While using the upper_bound() C ++ function, some important points need to be kept in mind. These are as follows:

• upper_bound() C++ returns an iteration that refers to the upper bound of the value provided in the range.
• This function works with the sorted sequence of elements only.
• Unlike lower_bound, the value pointed by the iterator returned by this function cannot be equivalent to the parameter val, it should be only greater.