visual walkthrough
Find First and Last Position of Element in Sorted Array
MediumLower / Upper Bound
Lower and upper bound together; very frequently asked.
The idea
A run of equal values in a sorted array has two boundaries. Each boundary is a "first index where …" question, which binary search answers.
The start is the first value ≥ target; the end is one before the first value ≥ target + 1.
Complexity
| approach | time | space |
|---|---|---|
| Scan everything | O(n) | O(1) |
| Two binary searches | O(log n) | O(1) |