First and Last Position

A list of whole numbers is sorted in ascending order. Values can repeat, so equal values sit next to each other in one run. Write first_and_last(nums, target) that returns [first, last]: the index where the run of target starts and the index where it ends. If target is not in the list, return [-1, -1].

Examples

first_and_last([2, 4, 4, 4, 7, 9], 4)   # returns [1, 3]
first_and_last([2, 4, 4, 4, 7, 9], 7)   # returns [4, 4]
first_and_last([2, 4, 4, 4, 7, 9], 5)   # returns [-1, -1]

The three 4s fill indexes 1, 2 and 3, so the answer is [1, 3]. A value that appears once starts and ends at the same index.

Constraints

• 0 <= len(nums) <= 100,000
• -10^9 <= nums[i], target <= 10^9
• nums is sorted in ascending order

Note

A run can fill almost the whole list, so stepping outward from one match can take 100,000 steps. Aim to find both ends in a few dozen looks, however long the run is.