int upperBound(vector<int> &arr, int x, int n){
// Write your code here.
int ans = n;
int low = 0;
int high = arr.size()-1;
while(low<=high){
int mid = (low+high)/2;
if(arr[mid] > x){
ans = mid;
high = mid-1;
}
else {
low = mid+1;
}
}
return ans;
}
Problem
Submissions
Hints & solutions
Discuss
Implement Upper Bound
Easy
0/40
Contributed by
138 upvotes
Problem statement
You are given a sorted array ‘arr’ containing ‘n’ integers and an integer ‘x’.Implement the ‘upper bound’ function to find the index of the upper bound of 'x' in the array.
1. The upper bound in a sorted array is the index of the first value that is greater than a given value.
2. If the greater value does not exist then the answer is 'n', Where 'n' is the size of the array.
3. Try to write a solution that runs in log(n) time complexity.
Example:
Input : ‘arr’ = {2,4,6,7} and ‘x’ = 5,
Output: 2
Explanation: The upper bound of 5 is 6 in the given array, which is at index 2 (0-indexed).
Detailed explanation ( Input/output format, Notes, Images )
Input format:
The first line contains two integers ‘n’ and ‘x’, denoting the number of elements in ‘arr’ and the value we need to find the upper bound of.
The second line contains ‘n’ integers, denoting the elements of ‘arr’.
Return the upper bound of ‘x’. Return ‘n’ if ‘x’ is greater than or equal to all the elements of ‘arr’.
Constraints:
1 <= ‘n’ <= 10^5
1 <= ‘x’ <= 10^9
1 <= ‘arr[i]’ <= 10^9
Time Limit: 1 sec
Sample Input 1:
5 7
1 4 7 8 10
Sample Output 1:
3
Explanation of sample output 1:
In the given test case, the lowest value greater than 7 is 8 and is present at index 3(0-indexed).
Sample Input 2:
5 10
1 2 5 6 10
Sample Output 2:
5
Sample Input 3:
7 5
1 5 5 7 7 9 10
Sample Output 3:
3
Hint
Hint 1
Hint 2
Iterate over all the elements of the given array.
Approaches (2)
Approach 1
Approach 2
Linear Search
Approach:
We can simply iterate through all the elements of the given array and return the index of the first value greater than ‘x’. If there’s no such index we can return ‘n’.
The steps are as follows:
function upper_bound(vector<int>&arr, int x, int n)
- for i from ‘0’ to ‘n-1’
- if(arr[i] > x)
- return i
- if(arr[i] > x)
- return n
Time Complexity
O(n), where ‘n’ is the size of array ‘arr’.
We are iterating through all the elements of array ‘arr’ of size ‘n’.
Hence, the time complexity is O(n).
Space Complexity
O(1).
We are not using any extra space.
Hence, the space complexity is O(1).
Code Solution
(100% EXP penalty)
Implement Upper Bound
All tags
Sort by
Interview problems
VERY EASY CODE ✅ || BEATS 93 % || O(log n) 🔥
40 views
0 replies
0 upvotes
Interview problems
Simple 🧠|| java || easy💯 || Upper Bound
public class Solution {
public static int upperBound(int []arr, int x, int n){
// Write your code here.
int ans=n;
int left=0;
int right=n-1;
while(left<=right)
{
int mid=(left+right)/2;
if(arr[mid]>x)
{
right=mid-1;
ans=mid;
}
else{
left=mid+1;
}
}
return ans;
}
}
26 views
0 replies
0 upvotes
Interview problems
Upper Bound C++ Solution.
int upperBound(vector<int> &arr, int x, int n){
int ans=n;
int low=0,high=n-1;
while(low<=high){
int mid=(low+high)/2;
if (arr[mid]>x){
ans=mid;
high=mid-1;
}
else{
low=mid+1;
}
}
return ans;
}
41 views
0 replies
0 upvotes
Interview problems
cpp easy solution for beginners
int upperBound(vector<int> &arr, int x, int n){
// Write your code here.
int low=0,high=n-1,ans=n;
while(low<=high)
{
int mid = (low+high) / 2;
if(arr[mid] > x)
{
ans = mid;
high = mid-1;
}
else
low = mid+1;
}
return ans;
}
23 views
0 replies
0 upvotes
Interview problems
optimal solution with o(logn) complexity ||c++
int upperBound(vector<int> &arr, int x, int n)
{
// Write your code here.
int low=0;
int high=n-1;
int ans=n;
while(low<=high)
{
int mid=low+(high-low)/2;
if(arr[mid]>x)
{
ans=mid;
high=mid-1;
}
else{
low=mid+1;
}
}
return ans;
}
13 views
0 replies
0 upvotes
Interview problems
Optimal Solution C++ || Binary Search without ans variable
int upperBound(vector<int> &arr, int x, int n){
// Write your code here.
int low = 0,high = n-1;
while(low<=high)
{
int mid = low+(high-low)/2;
if(arr[mid]>x){
high=mid-1;
}
else{
low = mid+1;
}
}
return low;
} 11 views
0 replies
0 upvotes
Interview problems
C++ way to solve
int upperBound(vector<int> &arr, int x, int n){
// Write your code here.
int ans=n;
int low=0;
int high=n-1;
int mid;
while(low<=high)
{
mid=(low+high)/2;
if(arr[mid]>x)
{
ans=mid;
high=mid-1;
}
else
{
low=mid+1;
}
}
return ans;
}
78 views
0 replies
0 upvotes
Interview problems
Oneliner code
int upperBound(vector<int> &arr, int x, int n){
// Write your code here.
int ans=upper_bound(arr.begin(),arr.end(),x)-arr.begin();
}
29 views
0 replies
0 upvotes
Interview problems
Easy solution using binary search
int upperBound(vector<int> &arr, int x, int n){
// Write your code here.
int upper = n;
int low = 0,high = n-1;
while(low<=high)
{
int mid = low+(high-low)/2;
if(arr[mid]>x){
upper = min(upper,mid);
high=mid-1;
}
else{
low = mid+1;
}
}
return upper;
} 128 views
0 replies
1 upvote
Interview problems
c++
int upperBound(vector<int> &arr, int x, int n) {
int low = 0, high = n - 1;
int ans = n;
while (low <= high) {
int mid = (low + high) / 2;
// maybe an answer
if (arr[mid] > x) {
ans = mid;
//look for smaller index on the left
high = mid - 1;
}
else {
low = mid + 1; // look on the right
}
}
return ans;
}
76 views
0 replies
1 upvote
1
2
3
4
C++ (g++ 5.4)
Console