The Core Idea

Binary search works on any space with a yes/no question that partitions it.

$1.$ Define $[low, high]$.

$2.$ Pick $mid = (low + high) / 2$.

$3.$ Check condition at $mid$.

$4.$ Narrow to $[low, mid]$ or $[mid+1, high]$.

$5.$ Repeat until one element.

$O(\log n)$: Each step halves the space. After $k$ steps: $n/2^k$ elements. When $n/2^k = 1$, $k = \log_2 n$.

Requires monotonic property: condition true on one side, false on the other.