Given an array nums sorted in non-decreasing order (duplicates allowed) and a value target, return the first and last index where target appears, as [first, last]. If target is missing, return [-1, -1]. The solution must run in O(log n).
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i], target <= 10^9
- `nums` is sorted in non-decreasing order
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The simple approach finds one copy with binary search and then expands outwards, but if the array is [8,8,8,...,8] that expansion is O(n). Instead, run two boundary searches. first is the lower bound of target (first index with value >= target). last is the lower bound of target + 1 minus one (the last index with value <= target). Each is O(log n). If first is out of range or nums[first] != target, the value is missing.
Algorithm
- Write a helper
lowerBound(x)that returns the first index withnums[i] >= x(ornif none). - Let
first = lowerBound(target). - If
first == nornums[first] != target, return[-1, -1]. - Let
last = lowerBound(target + 1) - 1and return[first, last].
O(log n)Space: O(1)target + 1 can overflow when target is Integer.MAX_VALUE. Either use a long, or write a second helper for "first index with value > target" instead.class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: def lower_bound(x): # first index with nums[i] >= x, or len(nums) if none lo, hi = 0, len(nums) while lo < hi: mid = (lo + hi) // 2 if nums[mid] < x: lo = mid + 1 else: hi = mid return loΒ first = lower_bound(target) if first == len(nums) or nums[first] != target: return [-1, -1] last = lower_bound(target + 1) - 1 return [first, last]