= Solution
For an ascending <sorted array>, maintain a candidate interval $[\ell,r]$ initially containing every index. Compare the target with the middle entry at $m=\lfloor(\ell+r)/2\rfloor$. Equality returns $m$; if the target is smaller, replace $r$ by $m-1$; if larger, replace $\ell$ by $m+1$. An empty interval reports absence.
The <loop invariant> is that any target occurrence still possible lies inside the candidate interval. <Sortedness> justifies discarding the appropriate half after each unequal comparison. The interval length decreases to at most half its previous length, establishing termination and correctness. After $t$ unsuccessful comparisons there are at most $n/2^t$ candidates, so at most $\lfloor\log_2n\rfloor+1$ comparisons suffice for $n\ge1$. Each iteration uses constant work on a random-access <array>. Thus \b[<binary search> takes $O(\log(n+1))$ <running time>], conventionally written $O(\log n)$ for nontrivial input sizes. Empty input is handled in constant time.
Back to article page
