= Solution
Use <binary search>. Maintain an inclusive candidate interval `[lo,hi]`, initially `[0,n-1]`. Compare the target `v` once with the middle entry; a ternary comparison returns less than, equal to, or greater than. Equality ends successfully. Otherwise <sortedness> permits discarding the middle entry and the entire half on the wrong side:
``
lo := 0; hi := n-1;
WHILE lo <= hi DO
mid := lo + (hi-lo) DIV 2;
IF v = S[mid] THEN RETURN TRUE
ELSIF v < S[mid] THEN hi := mid-1
ELSE lo := mid+1
END
END;
RETURN FALSE
``
The two written tests represent \i[one] ternary comparison whose result is then inspected. The <loop invariant> says that every occurrence of `v`, if any, lies in the candidate interval. Initially it is true. The order comparison and <sortedness> preserve it after either discard. If the interval becomes empty, the <loop invariant> proves absence.
A failed comparison reduces a candidate interval of size $m$ to at most $\lfloor m/2\rfloor$. For $n\geq1$, at most $\lfloor\log_2 n\rfloor+1$ comparisons are needed; an empty input needs none. Hence
$$
\boxed{C(n)\leq\lfloor\log_2 n\rfloor+1=O(\log n)\quad(n\geq1).}
$$
The claim counts comparisons. Indexed access to an <array> also makes elapsed running time logarithmic in the usual model; a <linked list> representation would not give the same access cost.
Back to article page
