Upper Bound

Upper bound finds the first element strictly greater than the target. Combined with lower bound, you can count occurrences.

Example: Upper bound of $5$ in $[1, 3, 5, 5, 7, 9]$ is index $4$ (the $7$).

Counting occurrences: The count of $5$ is upperBound(5) - lowerBound(5) = 4 - 2 = 2.

function upperBound(arr, target):
    low = 0
    high = arr.length

    while low < high:
        mid = low + (high - low) / 2
        if arr[mid] <= target:
            low = mid + 1
        else:
            high = mid

    return low

The only difference from lower bound: use <= instead of < when comparing.