Find First and Last Position of Element in Sorted Array

Problem

You are given an integer array nums sorted in non-decreasing order (duplicates allowed) and a value target. Return a two-element list [first, last] where first is the index of the first occurrence of target and last is the index of its last occurrence. If target does not appear in nums, return [-1, -1].

The required time complexity is O(log n).

Examples

• Input: nums = [5, 7, 7, 8, 8, 10], target = 8 → Output: [3, 4] (8 appears at indices 3 and 4.)
• Input: nums = [5, 7, 7, 8, 8, 10], target = 6 → Output: [-1, -1] (6 is absent.)
• Input: nums = [2, 2, 2, 2], target = 2 → Output: [0, 3] (The whole array is the target; the range spans everything.)

Constraints

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i], target <= 10^9
• nums is sorted in non-decreasing order (may contain duplicates, may be empty).
• Required time complexity: O(log n).

Think about it first

TL;DR

Two boundary binary searches (lower bound and upper bound) — O(log n) time, O(1) space.

Approach 1 — Brute force (linear scan)

Scan once, recording the first and last index where the target appears.

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        first, last = -1, -1
        for i, x in enumerate(nums):
            if x == target:
                if first == -1:
                    first = i
                last = i
        return [first, last]

Time O(n), space O(1). At n <= 10^5 this passes, but the problem demands O(log n) — and this is the follow-up interviewers actually care about.

Approach 2 — Binary search, then expand outward (tempting, still O(n))

The insight (and its flaw): a standard binary search finds some index holding the target in O(log n); walking left and right from it finds the edges. But the walk is linear in the number of duplicates — on nums = [2,2,2,2] you visit every element, so worst case is O(n). Worth writing to understand why the real solution needs two full binary searches.

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        lo, hi = 0, len(nums) - 1
        hit = -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                hit = mid
                break
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        if hit == -1:
            return [-1, -1]
        first = last = hit
        while first > 0 and nums[first - 1] == target:
            first -= 1
        while last < len(nums) - 1 and nums[last + 1] == target:
            last += 1
        return [first, last]

Walkthrough on [2, 2, 2, 2], target = 2: binary search hits mid=1 immediately, then the expansion loops crawl to first=0 and last=3 — 3 extra steps that grow linearly with the run length. Time O(log n + k) where k is the occurrence count, i.e. O(n) worst case; space O(1).

Approach 3 — Two boundary binary searches (lower + upper bound)

The insight: don’t search for the value, search for the edges. The predicate nums[i] >= target flips False→True exactly at the first occurrence (lower bound), and nums[i] > target flips at one past the last occurrence (upper bound). Each boundary is monotone, so each is findable by binary search that never stops early on a match — it keeps narrowing until the boundary is pinned. Lower/upper bound are the classical insertion-point binary searches (Python’s bisect_left / bisect_right).

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        def first_true(strict: bool) -> int:
            # smallest i with nums[i] > target (strict) or >= target (not strict)
            lo, hi = 0, len(nums)
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] > target or (not strict and nums[mid] == target):
                    hi = mid
                else:
                    lo = mid + 1
            return lo

        lower = first_true(strict=False)   # first index >= target
        upper = first_true(strict=True)    # first index >  target
        if lower == upper:                 # empty range: target absent
            return [-1, -1]
        return [lower, upper - 1]

Walkthrough on nums = [5, 7, 7, 8, 8, 10], target = 8:

Lower bound (>= 8): lo=0, hi=6 → mid=3, 8 >= 8 → hi=3; mid=1, 7 < 8 → lo=2; mid=2, 7 < 8 → lo=3 = hi. Lower = 3.

Upper bound (> 8): lo=0, hi=6 → mid=3, 8 not > 8 → lo=4; mid=5, 10 > 8 → hi=5; mid=4, 8 not > 8 → lo=5 = hi. Upper = 5.

lower=3 != upper=5 → return [3, 5 - 1] = [3, 4]. ✓

Time O(log n) (two independent halvings), space O(1). The one-liner version: bisect_left and bisect_right give lower and upper directly.

Common pitfalls

• Stopping the binary search as soon as nums[mid] == target — that finds an occurrence, not the first or last. Boundary searches must keep shrinking on equality.
• Returning [lower, upper] instead of [lower, upper - 1] — the upper bound points one past the last occurrence.
• Missing the absent-target check: when lower == upper the range is empty, and lower alone can be a perfectly valid-looking index (or len(nums) — an out-of-range read if you touch it).
• Forgetting the empty array: with the half-open [0, len(nums)) template, lower == upper == 0 falls out naturally, but an inclusive-hi template needs guarding.

Pattern takeaway

Duplicates turn “find the target” into “find the boundary”. The lower-bound / upper-bound pair — first index >= x, first index > x — carves out the exact run of any value in a sorted array, and their difference counts occurrences in O(log n). When a sorted-array problem mentions duplicates or asks for a first/last/leftmost/rightmost anything, reach for boundary binary search, not the equality-and-return kind.