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

Use binary search. Keep the half-open interval of candidate indices $[l,r)$, initially $[0,n)$. While it is nonempty, set $p=\lfloor (l+r)/2\rfloor$ and make one ternary comparison between the target $x$ and $S[p]$. Equality succeeds; a smaller target replaces $r$ by $p$; a larger target replaces $l$ by $p+1$. An empty interval certifies absence.

The loop invariant is that every possible occurrence of $x$ lies in the current interval. Its preservation follows from the ordering of $S$. After an unsuccessful comparison, at most $\lfloor (r-l)/2\rfloor$ candidates remain. Thus the maximum number of comparisons for $n\ge 1$ satisfies $C(n)\le 1+C(\lfloor n/2\rfloor )$ with $C(0)=0$, givingOne ternary comparison supplies all three outcomes; it is not counted as separate less-than and equality tests. The comparison model abstracts away any cost of navigating a non-random-access sequence. For an array, navigation also takes constant time per step.

The scan permits an arbitrary signed integer but prints ${\log }_{2}m$. That expression is undefined for $m\le 0$. The printed bound is proved below for positive $m$; for the stated signed domain the corresponding bound uses ${\log }_2\max (2,|m|)$. This is a source qualification, rather than an unreadable part of the question.^[ref]

Choose a fixed positive integer $k$ with $1/k\le ϵ$, and put $B=2^k$. For positive $m$, use coarse exponential bracketing: compare against $B,B^2,B^3,\dots$ until the first $B^j\ge m$. Equality determines $m$ immediately. Otherwise, $B^{j-1}<m<B^j$, except in the first interval where the lower bound is zero. Apply binary search to the remaining integer candidates.

There are at most $j$ bracketing comparisons and at most $kj+O(1)$ subsequent comparisons, because the interval width is at most $B^j=2^{kj}$. Minimality of $j$ gives $j\le ({\log }_{2}m)/k+1$. HenceThe additive constant may depend on the fixed $ϵ$, but is independent of $m$. Taking larger jumps in the bracketing phase reduces its leading comparison cost; the overshoot costs only the fixed number $k$ of extra binary search levels.

For signed inputs, first compare with zero. If negative, set $u=|m|$ conceptually and perform the same search for $u$: comparing $m$ with $-t$ yields the reversed outcome of comparing $u$ with $t$. Thus every test is still a permitted test of the sign of $m-x$. Return zero immediately on equality in the initial test. The corrected all-input bound isAll thresholds are exact integers, generated by repeated multiplication by $B$. Their arithmetic and storage costs are outside the requested comparison model; bounded machine arithmetic would not suffice for arbitrarily large $|m|$.

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.