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 / a

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.