 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 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\ge 1$, at most $\lfloor {\log }_{2}n\rfloor +1$ comparisons are needed; an empty input needs none. HenceThe 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.