= Solution
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\ge1$ satisfies $C(n)\le1+C(\lfloor n/2\rfloor)$ with $C(0)=0$, giving
$$
\boxed{C(n)\le\lfloor\log_2 n\rfloor+1=\log_2 n+O(1).}
$$
One <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.
Back to article page
