Upper Bound in Sorted Array - Visualization

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given a sorted array of integers and a target number x, your task is to find the upper bound of x in the array.

  • The upper bound of x is defined as the index of the first element in the array that is strictly greater than x.
  • If no such element exists (i.e., all elements are ≤ x), return the length of the array.

Examples❯

Input Array Key (x) Upper Bound Index Value at Upper Bound Description
[10, 20, 30, 40, 50] 30 3 40 First element greater than 30 is at index 3
[10, 20, 30, 40, 50] 45 4 50 50 is the first element greater than 45
[10, 20, 30, 40, 50] 50 5 - No element greater than 50, so return array length 5
[5, 10, 15] 1 0 5 All elements are greater, first is at index 0
[10] 5 0 10 Single element greater than key
[10] 10 1 - No element greater than 10
[10] 15 1 - All elements less than or equal to 15

Solution❯

Understanding the Problem

We are given a sorted array and a number x. Our goal is to find the upper bound of x. That means we want the index of the first element in the array that is strictly greater than x.

If no element in the array is greater than x, we should return the size of the array — indicating that all elements are less than or equal to x.

Step-by-Step Approach

We will use a technique called Binary Search, which is highly efficient on sorted arrays. This approach repeatedly splits the search range in half to quickly find the answer.

Step 1: Define Pointers

  • Set low = 0 (start of the array)
  • Set high = arr.length - 1 (end of the array)
  • Set ans = arr.length — default to the end of array in case we don’t find a greater element

Step 2: Apply Binary Search Logic

We run a loop while low ≤ high. On each iteration:

  • Calculate the mid index: mid = Math.floor((low + high) / 2)
  • If arr[mid] > x:
    • It is a valid candidate for upper bound
    • So update ans = mid
    • Then try to find a smaller valid index by moving high = mid - 1
  • Else (arr[mid] ≤ x):
    • We ignore this part of the array and move right: low = mid + 1

Step 3: Return the Result

After the loop ends, ans holds the index of the smallest number greater than x. If all elements are ≤ x, it remains at arr.length.

Example Walkthrough

Input: arr = [2, 4, 6, 10, 12], x = 6

Expected Output: 3 (since arr[3] = 10 is the first number > 6)

  1. Initial: low = 0, high = 4, ans = 5
  2. mid = 2 → arr[2] = 6 → not greater → move right (low = 3)
  3. mid = 3 → arr[3] = 10 → greater → ans = 3 → check left (high = 2)
  4. Loop ends → return ans = 3

Handling Edge Cases

  • Case 1: x is smaller than all elements
    Result: returns 0 (first element is upper bound)
  • Case 2: x is greater than all elements
    Result: returns arr.length (no element is greater)
  • Case 3: Array has duplicates
    It still finds the first element strictly greater than x
  • Case 4: Empty array
    Always return 0, as there are no elements to compare

This solution uses binary search, which is optimal for sorted arrays. Instead of checking each element, we skip half the array on each step — making it fast and efficient with a time complexity of O(log n).

Algorithm Steps❯

  1. Given a sorted array arr of N integers and an integer x.
  2. Initialize two pointers: low = 0 and high = arr.length - 1.
  3. Initialize ans = arr.length to track the possible answer.
  4. While low ≤ high:
  5. → Compute mid = Math.floor((low + high) / 2).
  6. → If arr[mid] > x, update ans = mid and set high = mid - 1.
  7. → Else, set low = mid + 1.
  8. After the loop, ans will hold the index of the upper bound.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int upperBound(int arr[], int n, int x) {
    int low = 0, high = n - 1, 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;
}

int main() {
    int arr[] = {1, 2, 4, 4, 5, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 4;
    printf("Upper Bound Index: %d\n", upperBound(arr, n, x));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)The target is immediately found at the mid index in the first comparison.
Average CaseO(log n)With each iteration, the search space is halved until the upper bound index is found.
Worst CaseO(log n)The binary search may continue until the search space is reduced to one element before finding the correct index or determining it does not exist.

Space Complexity❯

O(1)

Explanation: The algorithm uses a constant amount of extra space regardless of the input size. All operations are done in-place using variables like low, high, mid, and ans.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...