Problem

Given a sorted (non-decreasing) integer array arr of length n and an integer x, return the upper bound of x: the smallest index i such that arr[i] > x. If no such index exists, return n.

This is the counterpart of lower bound (first index with arr[i] >= x). Together they let you count occurrences of x as upperBound - lowerBound.

Input / Output

• Input: sorted array arr, integer x.
• Output: an index in [0, n].

Examples

Example 1 Input: arr = [1, 2, 2, 3, 3, 5], x = 3 Output: 5 Explanation: arr[5] = 5 is the first element strictly greater than 3.

Example 2 Input: arr = [1, 2, 2, 3, 3, 5], x = 5 Output: 6 Explanation: Nothing is greater than 5, so return n.

Example 3 Input: arr = [10, 20, 30], x = 5 Output: 0

Constraints

• 1 <= n <= 10^5
• -10^9 <= arr[i], x <= 10^9
• arr is sorted in non-decreasing order.

Approach

A linear scan works in O(n), but the array is sorted, so binary search gives O(log n):

lo = 0, hi = n - 1, ans = n
while lo <= hi:
    mid = lo + (hi - lo) / 2
    if arr[mid] > x:
        ans = mid        // candidate; look for an earlier one
        hi = mid - 1
    else:
        lo = mid + 1     // arr[mid] <= x, answer is to the right
return ans

The invariant is that every index >= ans satisfies arr[i] > x and every index < lo satisfies arr[i] <= x. When the loop ends, ans is the smallest qualifying index.

Equivalently, the answer is lowerBound(x + 1) for integers, which is why some libraries expose only one primitive.

Complexity

• Time: O(log n)
• Space: O(1)

Where it is used

Counting elements <= x, finding the insertion position that keeps stability (insert after duplicates), floor/ceil queries, and as the building block for problems such as "count of smaller numbers", "K-th element of two sorted arrays" and many binary-search-on-answer problems.

Reference solution (Python)

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

Test cases

Input	Expected
[1,2,2,3,3,5], x=3	5
[1,2,2,3,3,5], x=5	6
[10,20,30], x=5	0
[1,1,1], x=1	3