Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 5 / c / 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 withThe 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.