Find First and Last Position With Two Boundary Searches

This one is a Medium-rated classic reported from Meta, Google, LinkedIn interviews: "Find First and Last Position". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Modified Binary Search pattern on sight. Part 3 of 11 in the Modified Binary Search arc.

The Problem

Given a sorted array with duplicates and a target, return the first and last index of the target, or [-1, -1]. O(log n) required — expanding linearly around a found match degrades to O(n) on arrays like all-eights and is the specific trap this question sets.

Input:  nums = [5, 7, 7, 8, 8, 10], target = 8
Output: [3, 4]

Recognizing the Modified Binary Search Pattern

Binary search is not about sorted arrays — it is about any monotonic predicate: if the answer space splits into a false-region followed by a true-region, you can halve it. FAANG interviews rarely ask the textbook version; they ask rotated arrays, boundary-finding, and search-on-the-answer problems where the array being searched is conceptual. Getting the loop invariant right is the whole game.

A range of equal values has two boundaries, and each boundary is its own binary search: lower bound for the left edge, and lower bound of target + 1, minus one, for the right. Duplicates plus O(log n) is always a boundary-search cue.

The Approach

Run lower_bound(target). If it lands out of range or on a different value, the target is absent. Otherwise the right edge is lower_bound(target + 1) - 1 — reusing the same function twice is cleaner than writing symmetric left/right variants, and integer inputs make the plus-one trick valid.

If values were floats, plus-one breaks — you would write an explicit upper bound. Preempting that with one sentence is what senior sounds like.

Python Solution

def search_range(nums: list[int], target: int) -> list[int]:
    """First and last index of target in sorted nums, else [-1, -1]."""

    def lower_bound(t: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < t:
                lo = mid + 1
            else:
                hi = mid
        return lo

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

Complexity

• Time: O(log n) — two boundary searches
• Space: O(1) — index arithmetic

Interview Tips and Follow-Ups

• Count occurrences of target is this question minus the formatting: upper minus lower. Reported as a Google phone screen in its own right.
• Explain why find-then-expand is O(n) worst case — interviewers ask candidates to critique the naive answer explicitly.
• With bisect: bisect_left and bisect_right give both edges directly; knowing the mapping to stdlib is a plus.

If this clicked, continue the Modified Binary Search arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.