Given a sorted array of integers arr and a target value x, find the index of the upper bound of x. The upper bound is defined as the index of the first element in the array which is strictly greater than x. If no such element exists because all elements are smaller than or equal to x, return the size of the array N.
Example 1
Input: arr = [1, 3, 5, 7, 9, 11], x = 5
Output: 3
Explanation: The first element that is strictly greater than 5 is 7, which is located at index 3.
Example 2
Input: arr = [1, 3, 5, 5, 5, 9], x = 5
Output: 5
Explanation: The first element strictly greater than 5 is 9, which is located at index 5, skipping past all the duplicate 5s.
Brute Force Approach
The most direct idea is to move from left to right and stop at the first position where the value becomes strictly greater than X.
This works because the array is sorted, so the first such position is automatically the correct upper bound.
If the loop finishes without finding a larger value, that means every element is smaller than or equal to X, so the answer must be the length of the array.
Algorithm
Start from index
0and check each element one by one.If the current element is greater than
X, return that index immediately because it is the first valid upper bound position.If no such element is found after scanning the whole array, return the length of the array.
Key Points
If every element is smaller than or equal to
X, returnn.If
Xis smaller than the first element, the answer is0.If duplicate values equal to
Xexist, all of them must be skipped.
Dry Run
Upper Bound Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the first index where the array value is strictly greater than x. */ int upperBound(vector<int>& arr, int x) { // Check each position from left to right. for (int i = 0; i < (int)arr.size(); i++) { // The first value greater than x is the upper bound. if (arr[i] > x) { return i; } } return (int)arr.size(); }};// Driver code startsint main() { vector<int> arr = {2, 3, 7, 10, 11, 11, 25}; int x = 11; Solution obj; cout << obj.upperBound(arr, x) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), N is the length of array, because in the worst case the whole array may need to be scanned.
Space Complexity: O(1), because only a loop variable is used.
Optimal Approach
The useful observation is this: if arr[mid] is already greater than X, that index might be the answer, but there may still be another valid index on the left side.
So that position should be remembered, and the search should continue toward the left half.
If arr[mid] is smaller than or equal to X, then mid and everything before it become useless for upper bound, because none of them can be the first index with arr[index] > X.
This is why upper bound feels very close to lower bound, but the comparison changes. Lower bound checks for >= X, while upper bound checks for > X.
Algorithm
Start with two pointers,
lowat0andhighat the last index, because the answer can lie anywhere in the array.Keep a variable
answeras the length of the array. This is useful because if no valid index is found, that default value itself becomes the final answer.Find the middle index using
mid = low + (high - low) / 2so the middle position is calculated safely.If
arr[mid] > X, storemidinanswerbecause it is a valid upper bound candidate, then move left to check whether an even smaller valid value exists.If
arr[mid] <= X, move right because the upper bound cannot lie atmidor anywhere before it.Continue until
lowbecomes greater thanhigh.Return
answer.
Key Points
If every element is smaller than or equal to
X, returnN.If
Xis smaller than the first element, the answer is0.If duplicate values equal to
Xexist, the answer must be the first index after the last such duplicate.
Dry Run
Upper Bound Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the first index where the array value is strictly greater than x. */ int upperBound(vector<int>& arr, int x) { // Left boundary of the current search range. int low = 0; // Right boundary of the current search range. int high = (int)arr.size() - 1; // if no upper bound is found size of arr is ans int answer = (int)arr.size(); // Keep searching while a valid range still exists. while (low <= high) { // Calculate the middle index safely. int mid = low + (high - low) / 2; // This index is valid, so store it and // try to find an earlier one. if (arr[mid] > x) { answer = mid; high = mid - 1; } else { // Values up to mid are too small or equal, so move to the right half. low = mid + 1; } } return answer; }};// Driver code startsint main() { vector<int> arr = {2, 3, 7, 10, 11, 11, 25}; int x = 11; Solution obj; cout << obj.upperBound(arr, x) << endl; return 0;}Complexity Analysis
Time Complexity: O(log N), N is the length of array, because the search range becomes half in each step.
Space Complexity: O(1), because only a few variables are used.
Interview follow-up Questions
Lower bound gives the first index where the value is greater than or equal to X. Upper bound gives the first index where the value is strictly greater than X.
Be the first to add a comment.