Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 5 / b

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 }_{2}n\rfloor +1$ comparisons suffice for $n\ge 1$. Each iteration uses constant work on a random-access array. Thus 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.