visual walkthrough
Search Insert Position
Lower bound: the first index whose value is ≥ target.
The idea
The answer is the first position whose value is at least the target: where it is, or where it would be inserted.
Binary search for that boundary: keep a range that always contains it, and halve it.
Complexity
| approach | time | space |
|---|---|---|
| Scan from the left | O(n) | O(1) |
| Binary search (lower bound) | O(log n) | O(1) |