Exercise 2: First Occurrence

Your Task

Write a function first_occurrence(nums, target) that returns the leftmost index of target in a sorted list that may contain duplicates.

Return -1 if target is not in the list.

---

Examples

print(first_occurrence([1, 2, 2, 2, 3, 4], 2))   # 1
print(first_occurrence([1, 2, 2, 2, 3, 4], 3))   # 4
print(first_occurrence([1, 2, 2, 2, 3, 4], 5))   # -1
print(first_occurrence([2, 2, 2, 2, 2], 2))       # 0

---

Expected Complexity

	Complexity
Time	O(log n)
Space	O(1)

---

Approach

Standard binary search finds a match — but not necessarily the leftmost one. The trick is to keep searching left even after you find a match:

1. Set lo = 0, hi = len(nums) - 1, result = -1
2. While lo <= hi:
   • Compute mid = (lo + hi) // 2
   • If nums[mid] == target → record result = mid, then set hi = mid - 1 to look further left
   • If nums[mid] < target → set lo = mid + 1
   • If nums[mid] > target → set hi = mid - 1
3. Return result

---

Starter Code

def first_occurrence(nums, target):
    pass

print(first_occurrence([1, 2, 2, 2, 3, 4], 2))   # 1
print(first_occurrence([1, 2, 2, 2, 3, 4], 3))   # 4
print(first_occurrence([1, 2, 2, 2, 3, 4], 5))   # -1
print(first_occurrence([2, 2, 2, 2, 2], 2))       # 0

---

Hints