Find first and last position of element in sorted array

Given a sorted array that may contain duplicates, return the first and last index of the target, or [-1, -1] if it is absent, in O(log n).

Before you code

Finding any match and then scanning left and right is O(n) when the target fills the array. Two boundary searches answer it in O(log n) whatever the count.

Hints

1. First index: lower_bound(nums, target). Check that it is in range and holds the target.
2. Last index: upper_bound(nums, target) - 1.
3. Both searches never return early; they run until lo == hi.

Production & complexity notes

When solving Find first and last position of element in sorted array on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Lower and upper bounds to reinforce the underlying pattern.

What it practices

Lower and upper bounds, from Lower and upper bounds.