Find First Occurrence in a Sorted List
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.