💡 Suggested Approach & Sample Answer
Optimal Modified Binary Search Approach:
- Execute two targeted binary searches: one finding the leftmost boundary, and one finding the rightmost boundary.
def search_range(nums: list[int], target: int) -> list[int]:
def find_bound(is_first: bool) -> int:
left, right = 0, len(nums) - 1
bound = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
bound = mid
if is_first:
right = mid - 1 # Keep searching left
else:
left = mid + 1 # Keep searching right
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return bound
start = find_bound(True)
if start == -1:
return [-1, -1]
end = find_bound(False)
return [start, end]
Complexity & Key Logic:
- Time Complexity: O(log N) using two standard binary search passes.
- Space Complexity: O(1) constant auxiliary space.
- Algorithm Details:
- When nums[mid] == target, record mid and continue narrowing the search boundary (right = mid - 1 for first, left = mid + 1 for last).