Lower_bound and Upper_bound
Hard
C++
STL
50 views
Problem Statement
Find position to insert element to keep sorted order.
Real Life: Finding where to place book in sorted shelf.
Real Life: Finding where to place book in sorted shelf.
Input Format
An integer n (size of sorted array)
Then n integers (sorted in ascending order)
Then an integer x (element to insert)
Then n integers (sorted in ascending order)
Then an integer x (element to insert)
Output Format
Position (index) where x should be inserted to keep the array sorted
(0-based index)
(0-based index)
Example
5 1 3 5 7 9 6
3
Constraints
• n ≥ 1
• Array is already sorted
• Use linear or binary logic
• Array is already sorted
• Use linear or binary logic
Concept Explanation
To keep the array sorted, the new element must be placed
before the first element that is greater than or equal to it.
This is like finding the correct place for a book on a sorted shelf.
before the first element that is greater than or equal to it.
This is like finding the correct place for a book on a sorted shelf.
Step-by-Step Explanation
1.Take input size n.
2.Read the sorted array.
3.Take input element x.
4.Start from index 0.
5.Compare x with each array element:
• If x ≤ arr[i], then position is i.
6.If x is greater than all elements:
• Position is n (insert at end).
7.Print the position.
2.Read the sorted array.
3.Take input element x.
4.Start from index 0.
5.Compare x with each array element:
• If x ≤ arr[i], then position is i.
6.If x is greater than all elements:
• Position is n (insert at end).
7.Print the position.
Concept Explanation
To keep the array sorted, the new element must be placed
before the first element that is greater than or equal to it.
This is like finding the correct place for a book on a sorted shelf.
before the first element that is greater than or equal to it.
This is like finding the correct place for a book on a sorted shelf.
Step-by-Step Explanation
1.Take input size n.
2.Read the sorted array.
3.Take input element x.
4.Start from index 0.
5.Compare x with each array element:
• If x ≤ arr[i], then position is i.
6.If x is greater than all elements:
• Position is n (insert at end).
7.Print the position.
2.Read the sorted array.
3.Take input element x.
4.Start from index 0.
5.Compare x with each array element:
• If x ≤ arr[i], then position is i.
6.If x is greater than all elements:
• Position is n (insert at end).
7.Print the position.
Input / Output Format
Input Format
An integer n (size of sorted array)
Then n integers (sorted in ascending order)
Then an integer x (element to insert)
Then n integers (sorted in ascending order)
Then an integer x (element to insert)
Output Format
Position (index) where x should be inserted to keep the array sorted
(0-based index)
(0-based index)
Constraints
• n ≥ 1
• Array is already sorted
• Use linear or binary logic
• Array is already sorted
• Use linear or binary logic
Examples
Input:
5
1 3 5 7 9
6
Output:
3
Example Solution (Public)
void stl_q14_bounds() {
vector<int> numbers = {10, 20, 30, 30, 40, 50};
auto lower = lower_bound(numbers.begin(), numbers.end(), 30);
auto upper = upper_bound(numbers.begin(), numbers.end(), 30);
cout << "Lower bound of 30 at position: " << (lower - numbers.begin()) << endl;
cout << "Upper bound of 30 at position: " << (upper - numbers.begin()) << endl;
}
Official Solution Code
void stl_q14_bounds() {
vector<int> numbers = {10, 20, 30, 30, 40, 50};
auto lower = lower_bound(numbers.begin(), numbers.end(), 30);
auto upper = upper_bound(numbers.begin(), numbers.end(), 30);
cout << "Lower bound of 30 at position: " << (lower - numbers.begin()) << endl;
cout << "Upper bound of 30 at position: " << (upper - numbers.begin()) << endl;
}
Please login to submit solutions.