Find First and Last Position of Element in Sorted Array

The natural first idea: walk the array once, remembering the first and last index where the value equals target. Because the array is non-decreasing, the moment a value exceeds target we can stop — nothing further right can equal it. This is correct but linear, and the problem explicitly demands better, so treat it as the baseline the binary-search solution improves on.

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        first = -1
        last = -1
        for i, num in enumerate(nums):
            if num == target:
                if first == -1:
                    first = i
                last = i
            elif num > target:
                # Non-decreasing: no later element can equal target.
                break
        return [first, last]

Why it is linear: each element is inspected at most once and the early exit only shortens the work, so the worst case (all values below target) is one full pass of n steps. Only two integer variables are kept, so extra space is O(1).

Do not try to find an occurrence and expand outward — that expansion is O(n) when the array is all target. Instead, binary-search the two boundaries directly with a single reusable routine, lower_bound(x): the first index whose value is at least x.

The routine keeps a half-open window [lo, hi) that always contains the answer. Probe mid = (lo + hi) // 2:

• if nums[mid] < x, then mid and everything left of it is too small, so set lo = mid + 1;
• otherwise nums[mid] >= x, so mid is a legitimate candidate (it might be the first one), so set hi = mid — keeping mid inside the window.

The loop ends when lo == hi, and that shared index is the boundary. Calling it twice gives left = lower_bound(target) and right = lower_bound(target + 1); if left == right the target is absent, otherwise the answer is [left, right - 1].

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        def lower_bound(x: int) -> int:
            """First index i with nums[i] >= x, or len(nums) if none exists."""
            lo, hi = 0, len(nums)
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] < x:
                    lo = mid + 1   # mid and everything left of it is too small
                else:
                    hi = mid       # mid is a candidate; keep it in the window
            return lo

        left = lower_bound(target)
        right = lower_bound(target + 1)   # first index strictly greater than target
        if left == right:
            return [-1, -1]               # no element equals target
        return [left, right - 1]

Why it is correct: after every iteration the window [lo, hi) still contains the first index with nums[i] >= x — either that index was already below hi, or it sits at or after the new lo. When the window collapses to a single point, that point is the boundary. In the target case, lower_bound(target) is the first index equal to target (or the first greater value), and lower_bound(target + 1) - 1 is the last index equal to target. They coincide exactly when target never appears, which is the [-1, -1] case.

Why it is logarithmic: each pass halves the window, so a single lower_bound costs O(log n); two of them cost 2·O(log n) = O(log n). Only a handful of index variables are stored, so space is O(1).

Trace it on nums = [5, 7, 7, 8, 8, 10], target = 8 — watch the candidate window collapse in each pass, and note that first is locked in before the second search begins: