Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Implement Upper Bound

EASYProblemSolveExternal Links

Description

Given a sorted array of integers arr[] and an integer target, find the upper bound of target in the array.

The upper bound is defined as the smallest index in the sorted array where the element is strictly greater than the given target.

If all elements in the array are smaller than or equal to the target, the upper bound is the length of the array (meaning no element qualifies, so the answer points past the last index).

Examples

Example 1

Input: arr = [2, 3, 7, 10, 11, 11, 25], target = 9

Output: 3

Explanation: We need the smallest index where the element is strictly greater than 9. Looking at the array: 2 ≤ 9, 3 ≤ 9, 7 ≤ 9, but 10 > 9. The element 10 is at index 3, so the upper bound is 3.

Example 2

Input: arr = [2, 3, 7, 10, 11, 11, 25], target = 11

Output: 6

Explanation: We need the first element strictly greater than 11. Elements 2, 3, 7, 10 are all ≤ 11. Both 11s at indices 4 and 5 are equal to 11 — equal does NOT count, we need strictly greater. The element 25 at index 6 is the first one strictly greater than 11, so the upper bound is 6.

Example 3

Input: arr = [2, 3, 7, 10, 11, 11, 25], target = 100

Output: 7

Explanation: Every element in the array is ≤ 100. No element is strictly greater than 100. In this case, the upper bound equals the length of the array (7), indicating that the target would be placed after all existing elements.

Constraints

  • 1 ≤ arr.size() ≤ 10^6
  • 1 ≤ arr[i] ≤ 10^6
  • 1 ≤ target ≤ 10^6
  • The array is sorted in non-decreasing order.

Editorial

Brute Force

Intuition

The simplest way to find the upper bound is a straightforward linear scan. Since we need the first element strictly greater than the target, we can walk through the array from left to right and stop as soon as we find an element that is greater than the target.

Think of it like walking along a row of numbered lockers in ascending order. You have a ticket with the number 9. You walk past lockers numbered 2, 3, 7 — they are all ≤ 9, so you keep going. The moment you reach locker 10, you stop because 10 > 9. That locker's position is your answer.

If you reach the end of the row without finding any locker with a number greater than your ticket, the answer is the length of the row — meaning the target would be placed after all existing elements.

Step-by-Step Explanation

Let's trace through arr = [2, 3, 7, 10, 11, 11, 25], target = 9:

Step 1: Start at index 0. arr[0] = 2. Is 2 > 9? NO. Move to next.

Step 2: Index 1. arr[1] = 3. Is 3 > 9? NO. Move to next.

Step 3: Index 2. arr[2] = 7. Is 7 > 9? NO. Move to next.

Step 4: Index 3. arr[3] = 10. Is 10 > 9? YES! We found the first element greater than target.

Step 5: Return index 3.

Result: 3

Linear Scan — Finding First Element Greater Than Target — Walk left to right through the sorted array. The moment we find an element strictly greater than the target, we stop and return that index.

Algorithm

  1. Initialize answer = n (the length of the array).
  2. Iterate through the array from index 0 to n - 1:
    a. If arr[i] > target:
    • Set answer = i.
    • Break out of the loop (since the array is sorted, this is the smallest such index).
  3. Return answer.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int upperBound(vector<int>& arr, int target) {
        int n = arr.size();
        
        for (int i = 0; i < n; i++) {
            if (arr[i] > target) {
                return i;
            }
        }
        
        return n;
    }
};
class Solution:
    def upperBound(self, arr, target):
        n = len(arr)
        
        for i in range(n):
            if arr[i] > target:
                return i
        
        return n
class Solution {
    public int upperBound(int[] arr, int target) {
        int n = arr.length;
        
        for (int i = 0; i < n; i++) {
            if (arr[i] > target) {
                return i;
            }
        }
        
        return n;
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case, we scan through every element of the array. This happens when the target is greater than or equal to all elements (e.g., target = 100 in the array [2, 3, 7, 10, 11, 11, 25]). We visit all n elements before concluding there is no upper bound in the array.

Space Complexity: O(1)

We use only a single loop variable and no additional data structures. Space usage is constant regardless of input size.

Why This Approach Is Not Efficient

The linear scan does not take advantage of the fact that the array is sorted. With n up to 10^6, scanning every element means up to 10^6 operations in the worst case.

The sorted property gives us a powerful tool: if we look at a middle element and it is ≤ target, then every element to its left is also ≤ target (because the array is sorted). This means we can eliminate the entire left half in one step. Similarly, if the middle element is > target, it could be the answer, but we should also check the left half for a potentially smaller valid index.

This is the classic binary search pattern. Instead of checking elements one by one (O(n)), we halve the search space at each step, giving O(log n) — which for n = 10^6 means only about 20 comparisons instead of 1,000,000.

Optimal Approach - Binary Search

Intuition

Since the array is sorted, we can use binary search to efficiently find the upper bound. The key insight is to maintain a candidate answer and narrow down the search space:

  • If the middle element is greater than the target, it is a potential upper bound candidate. We record it and search the left half to see if there is an even smaller index with an element > target.
  • If the middle element is less than or equal to the target, it cannot be the upper bound. We discard the left half (including mid) and search the right half.

Imagine searching for a word in a dictionary. You open to the middle page. If the words on that page come after your target word, you know the answer is somewhere in the first half (or exactly at this page). If the words are before or at your target, you look in the second half. Each time you halve the remaining pages.

We initialize the answer to n (array length). If no element is found greater than the target during binary search, the answer remains n — indicating the upper bound is past the end of the array.

Step-by-Step Explanation

Let's trace through arr = [2, 3, 7, 10, 11, 11, 25], target = 11:

Step 1: Initialize low = 0, high = 6, answer = 7 (n).

Step 2: Compute mid = (0 + 6) / 2 = 3. arr[3] = 10.

  • Is 10 > 11? NO (10 ≤ 11). The upper bound cannot be at index 3 or anywhere to its left.
  • Move low = mid + 1 = 4.

Step 3: Compute mid = (4 + 6) / 2 = 5. arr[5] = 11.

  • Is 11 > 11? NO (11 is equal to 11, not strictly greater). Discard left half.
  • Move low = mid + 1 = 6.

Step 4: Compute mid = (6 + 6) / 2 = 6. arr[6] = 25.

  • Is 25 > 11? YES! This is a candidate. Record answer = 6.
  • Search left: high = mid - 1 = 5.

Step 5: low (6) > high (5). Loop ends.

Step 6: Return answer = 6.

Result: 6

Binary Search — Finding Upper Bound of 11 — Watch how binary search halves the search space at each step. When we find an element > target, we record it and search left for a smaller index. When element ≤ target, we search right.

Algorithm

  1. Initialize low = 0, high = n - 1, answer = n.
  2. While low ≤ high:
    a. Compute mid = low + (high - low) / 2.
    b. If arr[mid] > target:
    • This is a potential upper bound. Record answer = mid.
    • Search left for a possibly smaller valid index: high = mid - 1.
      c. Else (arr[mid] ≤ target):
    • arr[mid] and everything to its left cannot be the upper bound.
    • Search right: low = mid + 1.
  3. Return answer.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int upperBound(vector<int>& arr, int target) {
        int low = 0, high = arr.size() - 1;
        int answer = arr.size();
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (arr[mid] > target) {
                answer = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        
        return answer;
    }
};
class Solution:
    def upperBound(self, arr, target):
        low, high = 0, len(arr) - 1
        answer = len(arr)
        
        while low <= high:
            mid = low + (high - low) // 2
            
            if arr[mid] > target:
                answer = mid
                high = mid - 1
            else:
                low = mid + 1
        
        return answer
class Solution {
    public int upperBound(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int answer = arr.length;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (arr[mid] > target) {
                answer = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        
        return answer;
    }
}

Complexity Analysis

Time Complexity: O(log n)

At each step of the binary search, we halve the search space. Starting with n elements, after k steps we have n / 2^k elements. The loop ends when n / 2^k < 1, giving k = log₂(n). For n = 10^6, this means approximately 20 comparisons — compared to up to 10^6 with the brute force.

Space Complexity: O(1)

We use only three integer variables (low, high, answer) and no additional data structures. The space usage is constant regardless of input size.