= Solution
Use the <two-pointer technique>, starting at opposite ends of the ordered sequence:
``
l = 0
r = n - 1
while l < r:
s = S[l] + S[r]
if s == x: return (l, r)
if s < x: l = l + 1
else: r = r - 1
return NONE
``
If the sum is too small, every remaining pair using `l` has sum at most $S[l]+S[r]<x$, so discard `l`. If the sum is too large, every remaining pair using `r` has sum at least $S[l]+S[r]>x$, so discard `r`. The <loop invariant> says that every solution not already excluded has both indices in $[l,r]$. These two elimination arguments preserve it; at termination fewer than two positions remain.
Each unsuccessful iteration decreases $r-l$ by one. Therefore the <two-sum problem> is solved with
$$
\boxed{O(n)\ \text{time and }O(1)\ \text{auxiliary space}.}
$$
The condition `l < r` ensures distinct positions and handles $n<2$. Under the usual interpretation of “two distinct elements” as two different occurrences, equal values in different positions are allowed. If distinct numerical values are intended instead, reject an equality with $S[l]=S[r]$: sortedness then makes the entire remaining interval equal, so it contains no distinct-value solution. Both interpretations retain linear <time complexity>. The comparison assumes exact real-number operations, as in the stated <comparison model>.
Back to article page
