Topics › Binary Search › BS on 1D Arrays

Upper Bound

Easy TUF ID 82 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an array arr sorted in non-decreasing order (duplicates allowed) and an integer x. The upper bound of x is the smallest index i such that arr[i] > x, strictly greater. If no element is greater than x, return n, the length of the array. Equivalently, the upper bound is where x would be inserted to keep the array sorted while landing after every existing copy of x.

Constraints: 0 ≤ n ≤ 10^5, values and x fit in a 32-bit signed integer.

Example 1

arr = [1, 2, 2, 3, 3, 5], x = 2
answer = 3                // the 2s occupy indices 1..2; arr[3] = 3 is the first value > 2

Example 2

arr = [1, 2, 2, 3, 3, 5], x = 4
answer = 5                // 4 is absent; arr[5] = 5 is the first value > 4

Example 3

arr = [1, 2, 2, 3, 3, 5], x = 5
answer = 6                // nothing is > 5, so return n

Upper bound and lower bound (first index with arr[i] >= x) agree whenever x is absent; when x is present the lower bound points at its first copy and the upper bound points just past its last copy. The gap between them is therefore the number of copies, which is why both functions appear together so often.

Approach 1: Brute force, linear scan

Intuition. Scan from the left and stop at the first element that is strictly greater than x. Sorted order guarantees this is the smallest such index. Fall off the end, and the answer is n.

Algorithm.

1. For every index i from 0 to n - 1: if arr[i] > x, return i.
2. Return n.

static int bruteForce(int[] arr, int x) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > x) return i;
    }
    return arr.length;
}

Complexity. Time O(n) in the worst case, space O(1).

Approach 2: Optimal, binary search with a running answer

Intuition. The predicate arr[i] > x is false for some prefix of the sorted array and true afterwards: F F ... F T T ... T. We want the first T. Probing the middle tells us which side the boundary is on: a T at mid means the first T is at mid or to its left; an F means it is strictly to the right. We record every T we see in ans and keep moving left, so that the last recorded ans is the leftmost T. If we never see a T, ans keeps its initial value n.

The only difference from the lower bound is the comparison: > instead of >=. Everything else, including the proof of correctness, is identical.

Algorithm.

1. Set lo = 0, hi = n - 1, ans = n.
2. While lo <= hi:
   • mid = lo + (hi - lo) / 2.
   • If arr[mid] > x: set ans = mid, hi = mid - 1.
   • Else set lo = mid + 1.
3. Return ans.

static int optimal(int[] arr, int x) {
    int lo = 0, hi = arr.length - 1, ans = arr.length;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] > x) {
            ans = mid;            // mid qualifies; a smaller qualifying index may exist on the left
            hi = mid - 1;
        } else {
            lo = mid + 1;         // arr[mid] <= x, so every index <= mid is ruled out
        }
    }
    return ans;
}

Dry run on arr = [1, 2, 2, 3, 3, 5], x = 2:

The first probe landed on a copy of x itself. With >= (lower bound) that would have counted as a hit; with > it correctly counts as “not yet”, and the search moves right past all the 2s.

Complexity. Time O(log n), space O(1).

Approach 3: Optimal, reuse lower bound on x + 1

Intuition. For integers, “strictly greater than x” is the same as “greater than or equal to x + 1”. So upperBound(arr, x) == lowerBound(arr, x + 1). If you already have a well-tested lower bound, you get the upper bound for free, and you only need to maintain one binary search.

There is one trap: when x == Integer.MAX_VALUE, x + 1 overflows to Integer.MIN_VALUE, and the lower bound of the smallest possible integer is 0, which is wrong. But no int can be greater than Integer.MAX_VALUE, so the correct answer in that case is simply n. Handle it up front.

Algorithm.

1. If x == Integer.MAX_VALUE, return n.
2. Otherwise return lowerBound(arr, x + 1), where lowerBound is the standard half-open binary search for the first index with arr[i] >= value.

static int viaLowerBound(int[] arr, int x) {
    if (x == Integer.MAX_VALUE) return arr.length;   // no int is greater than x, and x + 1 would overflow
    return lowerBound(arr, x + 1);
}

private static int lowerBound(int[] arr, int x) {     // first index with arr[i] >= x, or n
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] >= x) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Complexity. Time O(log n), space O(1).

This trick only works for discrete types. For doubles there is no “next value after x” that is convenient to write, so use the direct > comparison from Approach 2 there.

Edge cases and pitfalls

• x is the maximum element. Nothing is strictly greater, so the answer is n, even though x is present. Compare Example 3.
• x smaller than every element. The first element already qualifies: answer 0.
• Empty array. Returns 0, which equals n.
• Duplicates. The upper bound skips over all copies of x. The test [1, 2, 2, 3, 3, 5], x = 2 returns 3, not 1 or 2.
• Mixing up > and >=. This is the single most common bug. Use > for upper bound, >= for lower bound, and check with an input where x is present: the two answers must differ by the number of copies.
• Overflow in x + 1. Only relevant for Approach 3; guard Integer.MAX_VALUE explicitly. The Java file tests [Integer.MIN_VALUE, Integer.MAX_VALUE] with x = Integer.MAX_VALUE and expects 2.
• Overflow in mid. Use lo + (hi - lo) / 2.

Related problems

• Lower Bound is the non-strict twin; read it first if the “first T” argument is new to you.
• First and last occurrence uses upperBound(x) - 1 as the index of the last copy of x.
• Count Occurrences in a Sorted Array is upperBound(x) - lowerBound(x).
• Search X in sorted array is the plain binary search both bounds are built from.