Upper Bound

Upper bound finds the first index at which elements become strictly greater than a value $x$ . It returns the smallest index $i$ such that

A[i] > x

If no such index exists, it returns $n$ .

This operation complements lower bound and allows precise range queries over equal values.

Problem

Given a sorted array $A$ of length $n$ and a value $x$ , find the smallest index $i$ such that

A[i] > x

Return $n$ if all elements are $\le x$ .

Key Idea

The predicate

A[i] > x

is monotone:

false for smaller indices
true for larger indices

Binary search isolates the first true position.

Algorithm

Use a half-open interval $[l, r)$ .

upper_bound(A, x):
    l = 0
    r = length(A)

    while l < r:
        m = l + (r - l) // 2

        if A[m] <= x:
            l = m + 1
        else:
            r = m

    return l

Example

Let

A = [1, 3, 3, 5, 7]

and

x = 3

Steps:

step	l	r	m	A[m]	action
1	0	5	2	3	move right
2	3	5	4	7	move left
3	3	4	3	5	move left

Return index $3$ .

Interpretation

All indices $< i$ satisfy $A[j] \le x$
All indices $\ge i$ satisfy $A[j] > x$

This splits the array into two regions.

Relation to Lower Bound

operation	condition	meaning
lower bound	$A[i] \ge x$	first occurrence of $x$ or insertion point
upper bound	$A[i] > x$	position after last occurrence of $x$

Range of equal elements:

[\text{lower\_bound}(x), \text{upper\_bound}(x))

Correctness

Invariant:

The answer remains in $[l, r)$

Each step eliminates half the interval while preserving:

left side contains only false values
right side contains possible true values

Termination at $l = r$ yields the first true index.

Complexity

case	time
all cases	$O(\log n)$

Space:

O(1)

Use Cases

Count elements $\le x$
Find right boundary of duplicates
Range counting and interval queries
Partitioning sorted data

Implementation

def upper_bound(a, x):
    l, r = 0, len(a)
    while l < r:
        m = l + (r - l) // 2
        if a[m] <= x:
            l = m + 1
        else:
            r = m
    return l

func UpperBound(a []int, x int) int {
    l, r := 0, len(a)
    for l < r {
        m := l + (r-l)/2
        if a[m] <= x {
            l = m + 1
        } else {
            r = m
        }
    }
    return l
}