Write search_range(nums: list[int], target: int) -> list[int].
nums is sorted in non-decreasing order and may contain long runs of equal values. Return [first, last]: the first and last index holding target. If target doesn't appear, return [-1, -1].
Example: nums = [1, 2, 2, 2, 5, 9], target = 2 gives [1, 3]; target = 9 gives [5, 5]; target = 4 gives [-1, -1].
Constraints: 0 <= len(nums) <= 10^6.
Must be O(log n) even when the run of target is huge: finding one match and then walking left and right is O(n) in the worst case and fails the performance test. Don't use the bisect module; the point is to write the search yourself.
C++ / Java: you write searchRangeAll(nums, targets), which returns search_range(nums, t) for every t in targets, in order, so the tests can run many searches on one big list. Write searchRange as a helper and call it in a loop.
Show hint
don't look for a match. Search directly for each boundary of the run: the first index whose value is not below target, and the first index whose value is above it.