Binary search: the halving recurrence

Binary search only works on a sorted array, and the whole point of it is that every comparison halves the part I still have to look at.

The invariant#

I keep a range that is known to contain the answer, if the answer exists at all:

let lo = 0;
let hi = arr.length - 1;

while (lo <= hi) {
  const mid = lo + Math.floor((hi - lo) / 2);
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) lo = mid + 1;
  else hi = mid - 1;
}
return -1;

The invariant is that the target, if present, sits inside $[lo, hi]$. Every branch either returns or shrinks that range, so the loop has to terminate.

Using lo + (hi - lo) / 2 instead of (lo + hi) / 2 avoids overflowing an integer when the indices are large.

The recurrence#

Let $T(n)$ be the work on a range of size $n$. Each step does a constant amount of work and then recurses on at most half the range:

I unfold it $k$ times:

The recursion bottoms out when $\frac{n}{2^k} = 1$, i.e. when $k = \log_2 n$

Base of the logarithm is irrelevant#

Different sources write $O(\log_2 n)$, $O(\ln n)$ or $O(\log_{10} n)$

And big-O throws constants away. So $O(\log n)$ is the honest statement.

Why the constant matters in practice#

The bound is good enough that the only thing left to worry about is getting the bounds right — lo <= hi versus lo < hi, mid + 1 versus mid. Those aren't sloppy details; a wrong one turns a $O(\log n)$ search into an infinite loop or a missed element.