← Binary Search (and its many faces)

Find First and Last Position in Sorted Array

Medium
Solve it on LeetCode ↗

The problem

In a sorted array with duplicates, return the first and last index of a target, or [−1, −1] — in O(log n).

Stuck? Reveal hints one at a time

How to approach it

  1. 1Write lowerBound(x): the smallest index with nums[index] ≥ x, using a half-open [lo, hi) search that never returns early.
  2. 2first = lowerBound(target); if out of range or nums[first] ≠ target → [−1, −1].
  3. 3last = lowerBound(target + 1) − 1.
  4. 4Return [first, last].

Key insight

Boundary binary search never breaks on equality — it keeps shrinking toward the edge. One reusable lowerBound answers both ends via the target+1 trick.

The solution

Watch out for

  • Returning early on nums[mid] === target finds A match, not the FIRST match.
  • Half-open [lo, hi) with lo < hi is the cleanest boundary-search idiom — memorize one form.