Module 12 · Binary Search and Monotone Answer Spaces

113. Upper Bound

Foundation · Download this solution · All solutions and shared helpers

Problem

Return the first index i with nums[i]>target in a nondecreasing integer list, or n if none exists. Equal values belong before the returned boundary. Empty input returns zero.

Examples

Example 1

upper_bound([1,3,3,3,8], 3)
=> 4

All copies of three lie before the boundary.

Example 2

upper_bound([3,3], 3)
=> 2

No strictly greater element exists.

Example 3

upper_bound([], 0)
=> 0

The empty boundary is zero.

Reveal the worked solution and reasoning

Why this mechanism works

Upper bound changes only the predicate from >= to >. That small change moves the boundary past the complete run of target values. The interval mechanics remain identical; copying a new pointer template is unnecessary.

State and boundaries

Indices before left have values<=target; indices from right onward have values>target. The first strictly greater boundary remains between them.

Protocol

Initialize left=0,right=n.
On nums[mid]>target move right to mid.
Otherwise move left to mid+1.
Return left at convergence.

Visualization

values: 1 3 3 3 8, target 3
predicate >3: F F F F T
upper bound: 4

Python implementation

def upper_bound(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > target:
            right = mid
        else:
            left = mid + 1
    return left

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

upper_bound([1,3,3,3,8], 3)

L2 upper_bound: left, right = 0, len(nums)
nums=[1, 3, 3, 3, 8]; target=3; left=0; right=5

L4 upper_bound: mid = (left + right) // 2
nums=[1, 3, 3, 3, 8]; target=3; left=0; right=5; mid=2

L8 upper_bound: left = mid + 1
nums=[1, 3, 3, 3, 8]; target=3; left=3; right=5; mid=2

L4 upper_bound: mid = (left + right) // 2
nums=[1, 3, 3, 3, 8]; target=3; left=3; right=5; mid=4

L6 upper_bound: right = mid
nums=[1, 3, 3, 3, 8]; target=3; left=3; right=4; mid=4

L4 upper_bound: mid = (left + right) // 2
nums=[1, 3, 3, 3, 8]; target=3; left=3; right=4; mid=3

L8 upper_bound: left = mid + 1
nums=[1, 3, 3, 3, 8]; target=3; left=4; right=4; mid=3

Result: 4. All copies of three lie before the boundary.

upper_bound([3,3], 3)

L2 upper_bound: left, right = 0, len(nums)
nums=[3, 3]; target=3; left=0; right=2

L4 upper_bound: mid = (left + right) // 2
nums=[3, 3]; target=3; left=0; right=2; mid=1

L8 upper_bound: left = mid + 1
nums=[3, 3]; target=3; left=2; right=2; mid=1

Result: 2. No strictly greater element exists.

Why the solution is correct

A false midpoint belongs to the <=target prefix and can be excluded with everything before it. A true midpoint bounds the >target suffix. Convergence identifies their unique boundary, including n when the suffix is empty.

Time and space

O(log(n+1)) time and O(1) auxiliary space.

Common mistakes

Reusing the lower-bound equality branch returns the beginning rather than the end of a duplicate run. right remains exclusive throughout.

Reasoning card

State: Indices before left have values<=target; indices from right onward have values>target. The first strictly greater boundary remains between them.

Invariant: All indices before left are <= target when the search ends.

Decision to rehearse: Change the predicate while keeping the same boundary-search skeleton.

Finish: Return left at convergence

Transfer exercise

Count occurrences of target as upper_bound-lower_bound without scanning the duplicate run.