Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input array is sorted, and the target value may appear many times in one contiguous block.

The task is not just to decide whether the target exists. It is to return the exact starting and ending indices of that block.

So the real question is:

how can a sorted array be used to find both boundaries in O(log n) time?

Why one ordinary binary search is not enough

A standard binary search can find one occurrence of the target, but that does not guarantee it found the first or last one.

For example, in [5, 7, 7, 8, 8, 10], searching for 8 might land on index 3 or 4. That is enough to prove the target exists, but it is not enough to answer the problem.

After finding one copy, there may still be matching values on the left or right.

That means the real work is not “find the target once.” It is “find the left boundary and the right boundary.”

The key insight

This problem becomes clean once it is reframed as two boundary searches:

  • find the first index where the value is at least target
  • find the first index where the value is greater than target

If the first search lands on a value that is not actually target, then the target does not exist at all.

If it does exist, then:

  • the first occurrence is the first index where value >= target
  • the last occurrence is one position before the first index where value > target

This is the same lower-bound / upper-bound pattern behind bisect_left and bisect_right.

How to derive the optimal solution

The sorted order gives a strong guarantee:

  • everything left of a cutoff is too small
  • everything right of a cutoff is large enough

That is exactly what binary search needs.

To find the first occurrence, keep shrinking toward the left whenever numbers[mid] >= target. To find the first value strictly greater than the target, keep shrinking toward the left whenever numbers[mid] > target.

Each search throws away half of the remaining range, so the total cost stays logarithmic:

  • Time: O(log n)
  • Extra space: O(1)

Even though there are two searches, O(log n) + O(log n) is still O(log n).

Best approaches

The cleanest approach is two binary searches on insertion points.

That version is better than:

  • scanning outward after finding one match, which can degrade to O(n)
  • collecting all matches, which uses extra space and ignores the sorted-array advantage

An alternative implementation is:

  1. run binary search to find any matching index
  2. run separate binary searches on the left and right sides to expand to the boundaries

That also works in O(log n), but the insertion-point version is usually simpler to reason about and easier to get correct.

Python solution

from typing import List


def find_first_index_at_least(numbers: List[int], target: int) -> int:
    """Return the first index whose value is >= target."""
    left_index = 0
    right_index = len(numbers)

    while left_index < right_index:
        middle_index = (left_index + right_index) // 2

        # Move right past values that are still too small.
        if numbers[middle_index] < target:
            left_index = middle_index + 1
        else:
            right_index = middle_index

    return left_index


def find_first_index_greater_than(numbers: List[int], target: int) -> int:
    """Return the first index whose value is > target."""
    left_index = 0
    right_index = len(numbers)

    while left_index < right_index:
        middle_index = (left_index + right_index) // 2

        # Move right past values that are <= target.
        if numbers[middle_index] <= target:
            left_index = middle_index + 1
        else:
            right_index = middle_index

    return left_index


class Solution:
    def searchRange(self, numbers: List[int], target: int) -> List[int]:
        first_match_index = find_first_index_at_least(numbers, target)

        if first_match_index == len(numbers):
            return [-1, -1]

        if numbers[first_match_index] != target:
            return [-1, -1]

        last_match_index = find_first_index_greater_than(numbers, target) - 1
        return [first_match_index, last_match_index]

The takeaway

The main pattern to remember is that many “find the range” problems are really asking for boundary searches, not exact-match searches.

Once the problem is translated into:

  • first index where value is big enough
  • first index where value is too big

the solution becomes a straightforward application of binary search.