Problem statement
Given a sorted array and a target, return the one-based positions of two numbers that add up to the target.
The lawful route
Use left and right boundaries. Compare their sum with the target and eliminate the boundary that cannot participate in a valid pair.
Invariant
If a valid pair exists, it remains inside the current left/right search window.
Proof vocabulary used
- Sorted Evidence
- Two Pointers
- Boundary Elimination
- Invariant
Complexity
Time O(n) · Space O(1)