Module 12 · Binary Search and Monotone Answer Spaces

112. Lower 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. Return n when no element qualifies. This insertion boundary is defined even when target is absent or the list is empty.

Examples

Example 1

lower_bound([1,3,3,3,8], 3)
=> 1

Equality keeps searching for an earlier qualifying position.

Example 2

lower_bound([1,2], 9)
=> 2

The answer may be the exclusive end boundary.

Example 3

lower_bound([], 1)
=> 0

The empty list has insertion boundary zero.

Reveal the worked solution and reasoning

Why this mechanism works

The predicate nums[i]>=target is false, then true. An equality is not a final answer because an earlier equal value may exist. Keep searching left on every true midpoint, while a false midpoint and all earlier indices can be excluded.

State and boundaries

Indices before left are known false; indices at or after right are known true when they exist. The first-true boundary lies between them.

Protocol

Start [left,right)=[0,n).
Test the midpoint predicate.
On True set right=mid.
On False set left=mid+1.
Return the meeting boundary.

Visualization

values: 1 3 3 3 8, target 3
predicate: F T T T T
first True index: 1

Python implementation

def lower_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.

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

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

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

L6 lower_bound: right = mid
nums=[1, 3, 3, 3, 8]; target=3; left=0; right=2; mid=2

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

L6 lower_bound: right = mid
nums=[1, 3, 3, 3, 8]; target=3; left=0; right=1; mid=1

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

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

Result: 1. Equality keeps searching for an earlier qualifying position.

lower_bound([1,2], 9)

L2 lower_bound: left, right = 0, len(nums)
nums=[1, 2]; target=9; left=0; right=2

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

L8 lower_bound: left = mid + 1
nums=[1, 2]; target=9; left=2; right=2; mid=1

Result: 2. The answer may be the exclusive end boundary.

Why the solution is correct

Monotonicity makes the whole prefix through a false midpoint false and the whole suffix from a true midpoint true. Each update narrows the unknown boundary region. When left==right, all earlier positions are false and that position is the first true one, or n if none exists.

Time and space

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

Common mistakes

Returning immediately on equality can choose a later duplicate. Treating n as an error discards a legitimate insertion boundary.

Reasoning card

State: Indices before left are known false; indices at or after right are known true when they exist. The first-true boundary lies between them.

Invariant: All indices before left are known too small.

Decision to rehearse: A true midpoint remains a candidate, so move right to middle.

Finish: Return the meeting boundary

Transfer exercise

Use lower bound to insert a value before all existing equal values.