Find First and Last Position of Element in Sorted Array
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found, return [-1, -1].
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i], target <= 10^9
nums = [5,7,7,8,8,10], target = 8[3,4]nums = [5,7,7,8,8,10], target = 6[-1,-1]Standard Binary Search stops the moment it finds a match. To find the "First" and "Last" positions, we have to change the rules: we have to be "Greedy."
If you find one instance of the target and then scan left and right to find the boundaries, your speed will plummet if the target appears thousands of times. On a large scale, this is as slow as a linear scan.
Instead of stopping, we use a specialized search:
1. To find the First Position: If we find a target at index 'mid', we save it as a "potential answer"—but we don't stop! We aggressively keep searching in the LEFT half to see if there is an even earlier occurrence.
2. To find the Last Position: We do the opposite. If we find a match, we save it and keep hunting in the RIGHT half for a later occurrence.
FUNCTION find_bound(is_first):
res = -1
left = 0, right = n-1
WHILE left <= right:
mid = left + (right-left) / 2
IF nums[mid] == target:
res = mid // Save current match
IF is_first: right = mid - 1 // Keep looking left
ELSE: left = mid + 1 // Keep looking right
...
RETURN [find_bound(true), find_bound(false)]By running binary search twice, we solve the problem in O(log N + log N), which is still logarithmic. This is optimal because it avoids the linear-scan bottleneck that occurs when multiple targets are clustered together. We use the sorted property to mathematically "squeeze" the target range from both ends.
Finding FIRST Occurrence
When finding the start of a range, finding the target isn't enough. We must continue searching to the left to ensure we have the very first one.