Skip to main content

Find First Occurrence in a Sorted List

Easy Subject: Binary Search
Time Complexity
O(log n)
Space Complexity
O(1)

Problem Description

Given a nondecreasing list and a target, return the index of its first occurrence. Return -1 if absent.

Example: [1, 2, 2, 2, 5] with target 2 returns 1.

Think about: Ordinary binary search may find any matching index. This version must keep searching left after a match.

Worked solution Open when you’re ready to compare your approach

Approach

Treat every matching midpoint as a candidate, then continue in the left half. If the midpoint is smaller than the target, the first match must lie to its right.

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

The search interval halves on each iteration: O(log n) time, O(1) space.

Check yourself: Why is the saved answer still valid after searching farther left?

Worked trace

Search for 2 in [1, 2, 2, 2, 5]. The middle index is 2, which matches. Record 2 as a possible answer, then continue only to the left. The next middle index is 0, holding 1, so move right. Index 1 matches and replaces the candidate. No positions remain to its left, so return 1. A normal binary search could stop at index 2 and miss the first occurrence.

Why it works and what to watch for

The list must already be sorted; otherwise discarding half of it has no justification. Whenever the middle value is smaller than the target, every value at or to its left is also too small. On a match, the current index is a valid candidate, while an earlier match may still exist to the left. That is why the algorithm keeps searching. A target absent from the list leaves the answer at -1. Empty input also returns -1. The loop halves the remaining search interval each time, taking O(log n) comparisons and O(1) space. Python's bisect_left gives the insertion position, but you must check that the returned position actually contains the target.