This is a simple application of binary search. The hard is part is how to tweak binary search to return the first (or last) index of a given target.

We do binary search as normal, and compare nums[mid] and target. If they are equal, we can’t just return mid, because this might be any of the targets in the array; we also can’t let high = mid or low = mid and keep searching, because it is possible that low and high will never meet in this case. Therefore, we must manually check if nums[mid] is the first (or last) target in the array. If so, just return mid; otherwise, let high = mid - 1 or low = mid + 1 and keep searching.

class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binarySearch(nums, target, low, high, first):
while low < high:
# print(low, high)
mid = (low + high) // 2
if first:
if nums[mid] == target and \
(mid == 0 or nums[mid-1] < target):
return mid
elif nums[mid] >= target:
high = mid - 1
else:
low = mid + 1
else:
if nums[mid] == target and \
(mid == len(nums)-1 or nums[mid+1] > target):
return mid
elif nums[mid] <= target:
low = mid + 1
else:
high = mid - 1
if low == high and nums[low] == target:
return low
else:
return -1
l = binarySearch(nums, target, 0, len(nums)-1, True)
r = binarySearch(nums, target, 0, len(nums)-1, False)
return [l, r]