Find First and Last Position of Element in Sorted Array

The machine must return the first and last index of a target in a sorted array with duplicates, or [-1,-1]. One binary search finds an occurrence, but not the boundary — so run two searches, each biased to one side. The first-occurrence search never stops at a match; it records it and keeps pushing left. The last-occurrence search pushes right.

def search_range(nums, target):
    def bound(left_bias):
        lo, hi = 0, len(nums) - 1
        idx = -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] > target:
                hi = mid - 1
            elif nums[mid] < target:
                lo = mid + 1
            else:
                idx = mid
                if left_bias:
                    hi = mid - 1
                else:
                    lo = mid + 1
        return idx
    return [bound(True), bound(False)]

Steps: (1) run a standard search that records the match, (2) after a match, keep searching the left side for the first occurrence, (3) repeat with the bias flipped for the last occurrence.

Time is O(log n) — two searches, each O(log n). Space is O(1).

Trickiest edge cases: target absent — both searches return -1, so the answer is [-1,-1]. An empty array short-circuits to [-1,-1]. When the array is all one value, the two searches must return opposite ends of the whole array, not the same index.