Practice
Resources
Contests
Online IDE
New
Free Mock
Events New Scaler
Practice
Improve your coding skills with our resources
Contests
Compete in popular contests with top coders
Events
Attend free live masterclass hosted by top tech professionals
New
Scaler
Explore Offerings by SCALER

# Upper & Lower bound

#### Lower Bound

The `lower_bound()` method in C++ is used to return an iterator pointing to the first element in the range [first, last) which has a value not less than val.
This means that the function returns the index of the next smallest number just greater than or equal to that number. If there are multiple values that are equal to val, lower_bound() returns the index of the first such value.
The elements in the range should be sorted.

`Syntax 1: ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, val); Syntax 2: ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, val, Compare comp);`

Parameters: The above methods accept the following parameters.

• first, last: The range used is [first, last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
• val: Value of the lower bound to be searched for in the range.
• comp: Binary function that accepts two arguments (the first of the type pointed by ForwardIterator, and the second, always val), and returns a value convertible to bool. The function shall not modify any of its arguments. This can either be a function pointer or a function object.

Return Value: An iterator to the lower bound of val in the range. If all the elements in the range compare less than val, the function returns last. If all the elements in the range are larger than val, the function returns a pointer to the first element.

Example:

`vector<int> v{1, 3, 6, 6, 8};vector<int>::iterator lower1, lower2, lower3;lower1 = lower_bound(v.begin(), v.end(), 4); // Index will be 2lower2 = lower_bound(v.begin(), v.end(), 1); // Index will be 0lower3 = lower_bound(v.begin(), v.end(), 9); // Index will be 5// To get the index do: lower1 - v.begin();cout<<"lower_bound for element 4 at position : "<<lower1 - v.begin()<<endl; // 2`

#### Upper Bound

`upper_bound()` is a standard library function in C++ defined in the header. It returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to val.

`Syntax 1:ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, val);Syntax 2:ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, val, Compare comp);`

Parameters: The above methods accept the following parameters.

• first, last: The range used is [first, last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
• val: Value of the upper bound to search for in the range.
• comp: Binary function that accepts two arguments (the first of the type pointed by ForwardIterator, and the second, always val), and returns a value convertible to bool. The function shall not modify any of its arguments. This can either be a function pointer or a function object.

Return type: An iterator to the upper bound of val in the range. If all the element in the range compare less than val, the function returns last.

Example:

`vector<int> v{1, 3, 6, 6, 8};vector<int>::iterator upper1, upper2, upper3;upper1 = upper_bound(v.begin(), v.end(), 6); // 4upper2 = upper_bound(v.begin(), v.end(), 1); // 1upper3 = upper_bound(v.begin(), v.end(), 4); // 2// To get the index do: upper1 - v.begin(); cout<<"upper_bound for element 6 at position : "<<upper1 - v.begin()<<endl; //4`

Note: We can also use lower and upper bound on set.

Syntax:

`Let s is a set.s.lower_bound(val);s.upper_bound(val);`

Try the following example in the editor below.

You are given N integers in sorted order not necessarily distinct. Also, you are given Q queries. In each query, you will be given an integer X and you have to tell whether that integer is present in the array. If so, you have to tell at which index (leftmost) it is present and if it is not present, you have to tell the rightmost index at which the current integer can be inserted such that the array remains sorted.

NOTE: You are not required to insert the value in the array. Array is not changed at any point.

Input Format

First line contains an integer N.
Second line contains N space-separarted integer in sorted order.
Third line contains an integer Q, the number of queries.
Each of the next Q lines contain a single integer X.

Output Format

For each query, print the index as described.

Sample Input

`65 15 21 21 22 225102123322`

Sample Output

`12604`
Hints
• Complete Solution

## Discussion

Free Mock Assessment
Fill up the details for personalised experience.
Phone Number *
OTP will be sent to this number for verification
+1 *
+1
Change Number
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
*Enter the expected year of graduation if you're student
Current Employer
Company Name
College/University Name
Job Title
Job Title
Software Development Engineer (Backend)
Software Development Engineer (Frontend)
Software Development Engineer (Full Stack)
Data Scientist
Android Engineer
iOS Engineer
Devops Engineer
Support Engineer
Research Engineer
Engineering Intern
QA Engineer
Co-founder
SDET
Product Manager
Product Designer
Backend Architect
Program Manager
Release Engineer