Module 12 · Binary Search and Monotone Answer Spaces

114. First and Last Target Position

Foundation · Download this solution · All solutions and shared helpers

Problem

Return [first,last], the inclusive zero-based positions of target in a nondecreasing integer list, or [-1,-1] if absent. Use logarithmic searches even when target occupies most of the list.

Examples

Example 1

target_range([5,7,7,8,8,10], 8)
=> [3, 4]

The exclusive end boundary five becomes last index four.

Example 2

target_range([5,7,7,8,8,10], 6)
=> [-1, -1]

The lower bound points to seven, so six is absent.

Example 3

target_range([], 0)
=> [-1, -1]

The lower boundary equals the list length.

Reveal the worked solution and reasoning

Why this mechanism works

The target run is the half-open interval [lower_bound(target),upper_bound(target)). Check whether its lower boundary actually points to target before converting the upper boundary to an inclusive last index. This composes two already-proven searches instead of expanding linearly from an arbitrary match.

State and boundaries

first is the first value>=target. end is the first value>target, so a present target occupies [first,end).

Protocol

Find lower bound.
Reject if it is n or its value is not target.
Find upper bound.
Return first and end-1.

Visualization

values: 5 7 7 8 8 10
target run: indices [3,5)
reported inclusive endpoints: [3,4]

Python implementation

from kata_112 import lower_bound
from kata_113 import upper_bound

def target_range(nums, target):
    first = lower_bound(nums, target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    return [first, upper_bound(nums, target) - 1]

Worked execution

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

target_range([5,7,7,8,8,10], 8)

L5 target_range: first = lower_bound(nums, target)
nums=[5, 7, 7, 8, 8, 10]; target=8; first=3

Result: [3, 4]. The exclusive end boundary five becomes last index four.

target_range([5,7,7,8,8,10], 6)

L5 target_range: first = lower_bound(nums, target)
nums=[5, 7, 7, 8, 8, 10]; target=6; first=1

Result: [-1, -1]. The lower bound points to seven, so six is absent.

Why the solution is correct

Sorted order places all equal targets in one consecutive run. Lower and upper bounds identify its exact two boundaries. The presence check distinguishes an empty target run from a real one, and subtracting one converts its exclusive end to the required inclusive index.

Time and space

O(log(n+1)) time and O(1) auxiliary space; the imported helpers are katas 112 and 113.

Common mistakes

Subtracting one before checking presence can invent a range for an absent value. Linear expansion around a found target can be O(n).

Reasoning card

State: first is the first value>=target. end is the first value>target, so a present target occupies [first,end).

Invariant: Each helper returns a mathematically defined boundary.

Decision to rehearse: Compose two boundary searches instead of special-case scanning.

Finish: Return first and end-1

Transfer exercise

Return the count or the half-open target interval directly, avoiding unnecessary conversion when the caller uses slicing.