# Upper Bound

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

```id="u9b2m4"
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

```id="c4p8w2"
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
```

```id="g7n1v6"
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
}
```