Module 12 · Binary Search and Monotone Answer Spaces

111. Exact Binary Search

Foundation · Download this solution · All solutions and shared helpers

Problem

Return an index of target in a nondecreasing integer list, or -1 if it is absent. With duplicates, return the first equality encountered by the specified midpoint search, not necessarily the first occurrence. Empty input is valid. Do not use a library search function.

Examples

Example 1

binary_search([1,3,5,7,9], 7)
=> 3

The target survives successive interval exclusions.

Example 2

binary_search([], 2)
=> -1

No midpoint is read from an empty list.

Example 3

binary_search([4], 3)
=> -1

The single rejected candidate is removed.

Reveal the worked solution and reasoning

Why this mechanism works

Sorted order allows one comparison to reject half the candidates. Use [left,right) so right is a boundary, not an element. After checking and rejecting mid, the remaining left candidates are [left,mid) and the remaining right candidates are [mid+1,right). Equality may terminate immediately.

State and boundaries

If target exists, at least one matching index remains in [left,right). mid is a valid index only while left<right.

Protocol

Start left=0,right=n.
While the interval is nonempty compute mid.
Return mid on equality.
Set left=mid+1 when nums[mid]<target.
Otherwise set right=mid.
Return -1 when candidates are exhausted.

Visualization

candidates: [left ........ right)
reject mid -> [left,mid) or [mid+1,right)
right itself is never a candidate cell

Python implementation

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

Worked execution

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

binary_search([1,3,5,7,9], 7)

L2 binary_search: left, right = 0, len(nums)
nums=[1, 3, 5, 7, 9]; target=7; left=0; right=5

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

L8 binary_search: left = mid + 1
nums=[1, 3, 5, 7, 9]; target=7; left=3; right=5; mid=2

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

L10 binary_search: right = mid
nums=[1, 3, 5, 7, 9]; target=7; left=3; right=4; mid=4

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

Result: 3. The target survives successive interval exclusions.

binary_search([], 2)

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

Result: -1. No midpoint is read from an empty list.

Why the solution is correct

A smaller midpoint value rules out every index through mid; a larger one rules out every index from mid onward. Each update preserves any possible match and strictly shrinks the interval. Equality returns a valid match, while an empty interval proves absence.

Time and space

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

Common mistakes

Using left=mid may not shrink a one-element interval. Reading nums[right] violates the exclusive boundary convention when right==n.

Reasoning card

State: If target exists, at least one matching index remains in [left,right). mid is a valid index only while left<right.

Invariant: Target, if present, remains inside the candidate interval.

Decision to rehearse: Choose one interval convention and preserve it consistently.

Finish: Return -1 when candidates are exhausted

Transfer exercise

Change the output to the first matching index. Explain why immediate return on equality no longer satisfies the contract.