Find First and Last Position of Element in Sorted Array

Intuition

A single lower-bound routine that finds the first index whose value is at least a given key is enough to solve the whole problem. Calling it with the target gives the start of the block. Calling it with target + 1 gives the first index strictly greater than the target, and stepping back one place from there lands on the end of the block. Reusing the same helper twice keeps the logic small and avoids off-by-one mistakes from writing two subtly different searches.

Algorithm walkthrough

1. 1Write a lowerBound helper that returns the first index i where nums[i] >= key using a half-open [lo, hi) search.
2. 2Compute start = lowerBound(target); this is the candidate first position.
3. 3If start is out of bounds or nums[start] does not equal target, the value is absent, so return [-1, -1].
4. 4Compute end = lowerBound(target + 1) - 1, which is the last index still equal to target.
5. 5Return [start, end].

Implementation

from typing import List


class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def lower_bound(key: int) -> int:
            lo, hi = 0, len(nums)
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] < key:
                    lo = mid + 1
                else:
                    hi = mid
            return lo

        start = lower_bound(target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        end = lower_bound(target + 1) - 1
        return [start, end]