Problem
Given a sorted integer array and a target, return the first and last index of the target. If the target is not present, return [-1, -1]. The solution must run in O(log n) time.
Approach
Write one helper that finds the lower bound: the first index whose value is at least a given number.
The lower bound of the target is the first position. If that index is past the end, or holds a different value, the target is missing.
The lower bound of target + 1 is the first index after the run of targets, so the last position is one before it. Two binary searches answer the question without scanning the run.
Solution
class Solution:
def searchRange(self, nums: list[int], target: int) -> list[int]:
def lower_bound(value: int) -> int:
low, high = 0, len(nums)
while low < high:
mid = (low + high) // 2
if nums[mid] < value:
low = mid + 1
else:
high = mid
return low
start = lower_bound(target)
if start == len(nums) or nums[start] != target:
return [-1, -1]
return [start, lower_bound(target + 1) - 1]Complexity
- Time: O(log n): two binary searches.
- Space: O(1).
Edge cases
- An empty array returns [-1, -1].
- A target that appears once returns the same index twice.
- A target smaller or larger than every value returns [-1, -1].