Find Upper Bound in Sorted Array

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.

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).

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.

#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;
}

#include <iostream>
#include <vector>
using namespace std;

int upperBound(vector<int>& arr, int x) {
    int low = 0, high = arr.size() - 1;
    int ans = arr.size();
    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() {
    vector<int> arr = {1, 2, 4, 4, 5, 7};
    int x = 4;
    cout << "Upper Bound Index: " << upperBound(arr, x) << endl;
    return 0;
}

def upper_bound(arr, x):
    low, high = 0, len(arr) - 1
    ans = len(arr)
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] > x:
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
    return ans

# Sample Input
arr = [1, 2, 4, 4, 5, 7]
x = 4
print("Upper Bound Index:", upper_bound(arr, x))

public class UpperBound {
    public static int upperBound(int[] arr, int x) {
        int low = 0, high = arr.length - 1;
        int ans = arr.length;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] > x) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 4, 5, 7};
        int x = 4;
        System.out.println("Upper Bound Index: " + upperBound(arr, x));
    }
}

function upperBound(arr, x) {
    let low = 0, high = arr.length - 1;
    let ans = arr.length;
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (arr[mid] > x) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return ans;
}

// Sample Input
const arr = [1, 2, 4, 4, 5, 7];
const x = 4;
console.log("Upper Bound Index:", upperBound(arr, x));

package main

import "fmt"

func upperBound(arr []int, x int) int {
    low, high := 0, len(arr)-1
    ans := len(arr)
    for low <= high {
        mid := (low + high) / 2
        if arr[mid] > x {
            ans = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return ans
}

func main() {
    arr := []int{1, 2, 4, 4, 5, 7}
    x := 4
    fmt.Println("Upper Bound Index:", upperBound(arr, x))
}

fn upper_bound(arr: &Vec<i32>, x: i32) -> usize {
    let (mut low, mut high) = (0, arr.len() as isize - 1);
    let mut ans = arr.len();
    while low <= high {
        let mid = (low + high) / 2;
        if arr[mid as usize] > x {
            ans = mid as usize;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    ans
}

fn main() {
    let arr = vec![1, 2, 4, 4, 5, 7];
    let x = 4;
    println!("Upper Bound Index: {}", upper_bound(&arr, x));
}

fun upperBound(arr: List<Int>, x: Int): Int {
    var low = 0
    var high = arr.size - 1
    var ans = arr.size
    while (low <= high) {
        val mid = (low + high) / 2
        if (arr[mid] > x) {
            ans = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return ans
}

fun main() {
    val arr = listOf(1, 2, 4, 4, 5, 7)
    val x = 4
    println("Upper Bound Index: ${upperBound(arr, x)}")
}

func upperBound(_ arr: [Int], _ x: Int) -> Int {
    var low = 0
    var high = arr.count - 1
    var ans = arr.count
    while low <= high {
        let mid = (low + high) / 2
        if arr[mid] > x {
            ans = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return ans
}

let arr = [1, 2, 4, 4, 5, 7]
let x = 4
print("Upper Bound Index:", upperBound(arr, x))

function upperBound(arr: number[], x: number): number {
    let low = 0, high = arr.length - 1;
    let ans = arr.length;
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (arr[mid] > x) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return ans;
}

const arr: number[] = [1, 2, 4, 4, 5, 7];
const x: number = 4;
console.log("Upper Bound Index:", upperBound(arr, x));

Time complexity

Space complexity

O(1)

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.