Practice
Resources
Contests
Online IDE
New
Free Mock
Scaler
Practice
Improve your coding skills with our resources
Contests
Compete in popular contests with top coders
Scaler
Explore Offerings by SCALER

Begin your success journey!

Sign Up using
Full name *
Email *
Password *

By creating an account, I acknowledge that I have read and agree to InterviewBit’s Terms and Privacy Policy .

Welcome back!

Log In using
Email *
Password *

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 2
lower2 = lower_bound(v.begin(), v.end(), 1); // Index will be 0
lower3 = 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); // 4
upper2 = upper_bound(v.begin(), v.end(), 1); // 1
upper3 = 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

6
5 15 21 21 22 22
5
10
21
23
3
22

Sample Output

1
2
6
0
4
Start solving Upper & Lower bound on Interview Code Editor
Hints
  • Complete Solution

Discussion


Loading...
Click here to start solving coding interview questions
Free Mock Assessment
Fill up the details for personalised experience.
All fields are mandatory
Current Employer *
Enter company name *
Graduation Year *
Select an option *
1992
1993
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
Phone Number *
OTP will be sent to this number for verification
+1 *
+1
Change Number
Phone Number *
OTP will be sent to this number for verification
+1 *
+1
Change Number
Graduation Year *
Graduation Year *
1992
1993
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
*Enter the expected year of graduation if you're student
Current Employer *
Company Name *
Please verify your phone number
Edit
Resend OTP
By clicking on Start Test, I agree to be contacted by Scaler in the future.
Already have an account? Log in
Free Mock Assessment
Instructions from Interviewbit
Start Test