Binary search is a powerful divide-and-conquer algorithm that finds elements in sorted arrays with O(log n) time complexity. But what happens when you need to find not just any occurrence of a target, but the first or last occurrence? This requires modifying the classic binary search algorithm.
In standard binary search, once we find our target, we return immediately. But when dealing with duplicate values, we might find a target in the middle of a sequence of identical elements. To find the boundaries of this sequence, we need to continue searching even after finding a match.
The key insight is to perform two separate binary searches:
This approach maintains the O(log n) time complexity while giving us precise boundary information.
For finding the first occurrence, the modification is subtle but crucial. When nums[mid] == target, instead of returning immediately, we save this position as a potential answer and continue searching the left half by setting right = mid - 1. This ensures we find the leftmost occurrence.
Similarly, for the last occurrence, when we find a match, we save the position and search the right half by setting left = mid + 1.
Both searches use the same binary search framework but with different behaviors when the target is found. This technique is fundamental in many algorithms that need to find ranges or boundaries in sorted data.
1def find_leftmost_occurrence(nums, target):
2 left, right = 0, len(nums) - 1
3 leftmost = -1
4
5 while left <= right:
6 mid = (left + right) // 2
7
8 if nums[mid] == target:
9 leftmost = mid # Save this position
10 right = mid - 1 # Continue searching left
11 elif nums[mid] < target:
12 left = mid + 1
13 else:
14 right = mid - 1
15
16 return leftmost