Finding First Occurrence
What You'll Learn
You'll learn how to modify binary search to find the leftmost (first) occurrence of a target value when duplicates exist in a sorted array.
The Problem with Standard Binary Search
Standard binary search finds a match, but when duplicates exist, you don't know if it's the first one. For example, in [1, 2, 4, 4, 4, 7, 9], searching for 4 might return index 2, 3, or 4—whichever the algorithm happens to land on first.
The Core Modification
To guarantee finding the first occurrence, we adjust the strategy:
- When we find a match, don't return immediately
- Instead, record that position as a potential answer
- Continue searching left (in the lower half) to see if an earlier occurrence exists
- Only stop when the search range is exhausted
Think of it like looking for the first page where a word appears in a dictionary. Even when you find it, you flip backward to make sure there isn't an earlier page with that same word.
The Algorithm
When arr[mid] == target:
- Save
midas a candidate result - Set
right = mid - 1(search the left half) - Continue the loop
When arr[mid] < target:
- Set
left = mid + 1(target must be to the right)
When arr[mid] > target:
- Set
right = mid - 1(target must be to the left)
The key difference from standard binary search: we don't stop at the first match—we keep narrowing left until we've confirmed no earlier occurrence exists.
Time Complexity
Still O(log n)—we're just being pickier about which match we accept.
Key Takeaway: To find the first occurrence in a sorted array with duplicates, continue searching left even after finding a match, treating each match as a "best so far" candidate until the search space is exhausted.