Ga naar inhoud

1. Binary Search

Binary search is one of the most fundamental algorithms in computer science: given a sorted array \(A[0..n-1]\) and a target value \(t\), it locates \(t\) — or confirms its absence — in \(O(\log_2 n)\) comparisons by repeatedly halving the candidate range. Knuth 1 traces the idea to the 1940s and notes that, while the principle is elementary, writing a provably correct implementation is surprisingly subtle: the first published bug-free iterative version did not appear until 1962. Cormen et al. 2 classify binary search as the paradigmatic example of the decrease-and-conquer strategy, in which a single comparison eliminates half the remaining search space.

Binary search is often superficially compared to the bisection method, but the two are categorically distinct. Binary search operates on a sorted discrete collection and produces an exact answer (an index or an absence flag); bisection operates on a continuous function and produces an approximation to a root, with a convergence guarantee grounded in the Intermediate Value Theorem. They share a geometric intuition but not a mathematical foundation.

1.1 Mathematical Foundation

1.1.1 Total Order and Sorted Sequences

Binary search requires the array elements to be drawn from a totally ordered set \((S, \leq)\), meaning the relation \(\leq\) is reflexive, antisymmetric, transitive, and total (every pair of elements is comparable). For any sorted array, the invariant

\[ \begin{equation} A[i] \leq A[j] \quad \forall\; 0 \leq i < j \leq n-1 \label{sorted_invariant} \end{equation} \]

holds. This invariant is the entire source of binary search's correctness: if \(A[m] < t\) (where \(m = \ell + \lfloor(h - \ell)/2\rfloor\) is the midpoint index, defined precisely in The Algorithm below), then every element at index \(\leq m\) is also \(< t\) by transitivity, allowing the left half to be discarded without inspection.

1.1.2 Comparison Complexity Lower Bound

Any algorithm that identifies a target in a sorted sequence using only comparisons must make at least \(\lfloor \log_2 n \rfloor\) comparisons in the worst case. This lower bound follows from the information-theoretic argument: each comparison has at most three outcomes (\(<\), \(=\), \(>\)), so a binary decision tree of depth \(d\) can resolve at most \(3 \cdot 2^{d-1}\) outcomes; to distinguish \(n\) positions plus an absence result requires depth at least \(\log_2(n+1)\). Binary search achieves this bound exactly, making it optimal among comparison-based search algorithms 3.

Decision tree argument

A comparison tree models the algorithm as a rooted tree whose internal nodes each represent one comparison \(A[m]\) vs \(t\). Each node has three outgoing edges corresponding to the outcomes \(A[m] < t\), \(A[m] = t\), and \(A[m] > t\). The \(=\) edge leads directly to a leaf (target found); the \(<\) and \(>\) edges recurse to child nodes or to a "not found" leaf. A tree of depth \(d\) has at most \(3 \cdot 2^{d-1}\) leaves (the root contributes 3 branches; each subsequent non-terminal level at most doubles the frontier of live nodes). To distinguish all \(n\) found positions plus one absent outcome requires at least \(n + 1\) reachable leaves, giving \(3 \cdot 2^{d-1} \geq n + 1\) and hence \(d \geq \log_2\!\bigl((n+1)/3\bigr) + 1\). For large \(n\) this simplifies to \(d \geq \log_2(n+1)\). Binary search constructs a tree that reaches exactly this depth, confirming the bound is tight.

1.2 The Algorithm

1.2.1 Iterative Formulation

Maintain two indices \(\ell\) (low) and \(h\) (high) representing the inclusive bounds of the current candidate interval:

\[ \begin{equation} \ell_0 = 0, \qquad h_0 = n - 1 \label{binary_search_init} \end{equation} \]
Index notation

Throughout this section a subscript \(k = 0, 1, 2, \ldots\) denotes the value of a variable at the start of iteration \(k\). Concretely: \(\ell_k\) is the lower bound of the candidate interval entering iteration \(k\); \(h_k\) is the upper bound; \(m_k\) is the midpoint computed during iteration \(k\). After the comparison, whichever of \(\ell\) or \(h\) needs updating is written as \(\ell_{k+1}\) or \(h_{k+1}\) — the value passed into iteration \(k+1\). The algorithm terminates at iteration \(k\) if either \(A[m_k] = t\) (found) or the updated interval satisfies \(\ell_{k+1} > h_{k+1}\) (absent).

At each iteration, compute the midpoint via integer arithmetic to avoid overflow 2:

\[ \begin{equation} m_k = \ell_k + \left\lfloor \frac{h_k - \ell_k}{2} \right\rfloor \label{binary_search_mid} \end{equation} \]

The update rule is a three-way branch:

\[ \begin{equation} (\ell_{k+1},\, h_{k+1}) = \begin{cases} (\ell_k,\; m_k - 1) & \text{if } A[m_k] > t \\ (\text{found at } m_k) & \text{if } A[m_k] = t \\ (m_k + 1,\; h_k) & \text{if } A[m_k] < t \end{cases} \label{binary_search_update} \end{equation} \]

Iteration terminates when a match is found or when \(\ell_k > h_k\), which signals that \(t \notin A\).

1.3 Complexity Analysis

1.3.1 Worst-Case Comparison Count

Each iteration reduces the interval width \(h_k - \ell_k + 1\) by (at least) half. Starting from width \(n\), the interval reaches width \(\leq 1\) after at most \(\lceil \log_2 n \rceil\) halvings. Knuth 1 gives the exact worst-case count as

\[ \begin{equation} C_{\text{worst}}(n) = \lfloor \log_2 n \rfloor + 1 \label{binary_search_worst} \end{equation} \]

comparisons, and the average count for a successful search (assuming uniform distribution over \(n\) elements) as

\[ \begin{equation} C_{\text{avg}}(n) = \frac{1}{n} \sum_{j=1}^{n} \lfloor \log_2 j \rfloor + 1 \approx \log_2 n - 1 \label{binary_search_avg} \end{equation} \]

Linear (sequential) search examines elements one by one, requiring \(O(n)\) comparisons on average and in the worst case. Binary search reduces this to \(O(\log_2 n)\). The practical impact is enormous: for \(n = 10^9\), linear search may require up to \(10^9\) comparisons; binary search requires at most \(30\).

\(n\) Linear (worst) Binary (worst)
16 16 4
1 024 1 024 10
\(10^6\) \(10^6\) 20
\(10^9\) \(10^9\) 30

1.4 Variants

1.4.1 Lower Bound and Upper Bound

Standard binary search finds any occurrence of \(t\). When duplicates are present, two specialised variants are needed 23:

  • Lower bound (lower_bound): returns the index of the first element \(\geq t\). If \(t\) is absent, returns the insertion point that preserves sorted order.
  • Upper bound (upper_bound): returns the index of the first element \(> t\). The range \([\text{lower_bound}(t),\, \text{upper_bound}(t))\) is the interval of all occurrences of \(t\).

Both require only the replacement of the equality check by a one-sided comparison, leaving the \(O(\log n)\) complexity unchanged.

1.4.2 Recursive Formulation

Binary search can equally be written recursively:

\[ \text{search}(A,\, t,\, \ell,\, h) = \begin{cases} -1 & \text{if } \ell > h \\ m & \text{if } A[m] = t, \quad m = \ell + \lfloor (h-\ell)/2 \rfloor \\ \text{search}(A,\, t,\, m+1,\, h) & \text{if } A[m] < t \\ \text{search}(A,\, t,\, \ell,\, m-1) & \text{if } A[m] > t \end{cases} \]
Scope of \(m\) across the branches

In the piecewise definition above, \(m\) is not independently defined in cases 3 and 4 — it is computed once at the start of each call as \(m = \ell + \lfloor(h - \ell)/2\rfloor\) (stated explicitly as part of case 2). All four cases then refer to this same value: case 1 checks whether the search interval is empty and returns \(-1\) (target absent); case 2 tests \(A[m] = t\) and returns the index \(m\) if so; cases 3 and 4 compare \(A[m]\) with \(t\) and recurse into the appropriate half, passing \(m+1\) or \(m-1\) as the new boundary to exclude the already-tested midpoint. The variable \(m\) is implicitly local to the current call and takes a fresh value in each recursive invocation.

The recurrence for the number of comparisons is \(T(n) = T(n/2) + 1\), \(T(1)=1\), where \(T(n/2)\) reflects the fact that each recursive call searches exactly half the remaining interval. The recurrence solves to \(T(n) = \lceil \log_2(n+1) \rceil\) by the Master Theorem — identical to the iterative form.

The recursive version incurs \(O(\log n)\) call-stack frames, giving it \(O(\log n)\) space instead of \(O(1)\) for the iterative version. For very large \(n\) this can matter in practice.

When the array size \(n\) is unknown or very large, binary search can be preceded by an exponential phase: examine \(A[1],\, A[2],\, A[4],\, A[8],\, \ldots\) until an element exceeding \(t\) is found, then apply binary search on the identified interval. The total work is \(O(\log i)\) where \(i\) is the position of \(t\) — useful for unbounded arrays or when the target is expected to be near the start 3.

1.4.4 Fractional Cascading

When the same target must be searched in \(k\) related sorted arrays simultaneously, fractional cascading reduces the total cost from \(O(k \log n)\) to \(O(k + \log n)\) by threading pointers between arrays. This technique is useful in computational geometry and range-tree data structures.

1.5 Limitations and Challenges

Binary search is only applicable if the following preconditions are met:

  1. Sorted order: The array must satisfy the invariant of Equation \eqref{sorted_invariant}. If the array is unsorted, binary search produces incorrect results without warning. Sorting costs \(O(n \log n)\), which dominates a single search; the algorithm is only worthwhile when many searches are performed on the same sorted data.

  2. Random-access indexing: Binary search computes \(A[m]\) in \(O(1)\) and thus requires a data structure supporting constant-time random access (arrays, vectors). It cannot be applied to linked lists without degrading to \(O(n)\) due to the cost of index traversal.

  3. Static data: Inserting or deleting elements requires re-sorting or using a dynamic structure (balanced BST, skip list), both of which add \(O(\log n)\) overhead per modification. For heavily mutable data, binary search on a raw array is inappropriate.

  4. Exact target required: Binary search finds elements equal to \(t\) exactly. Approximate matching (nearest neighbour, similarity search) requires different methods — k-d trees, LSH, or metric-space indices.

  5. Not for continuous domains: Binary search is not applicable to continuous root-finding problems; that is the domain of bracketing methods such as bisection.

1.6 Interactive Demonstration

The animation below shows binary search on a fixed sorted array of 16 integers. The target is highlighted in the header; each step shows the current \([\ell, h]\) interval (grey region) and the midpoint \(m\) (amber cell). Click Step to advance one comparison or Play to run automatically. A successful find lights the cell green; a failed search shades the last remaining cell red.

The target selector includes both present values (found) and absent values (marked absent in the dropdown) so you can observe both termination cases. The column indices shown below each cell correspond to the array positions \(A[0..15]\). The lo (blue) and hi (red) triangles bound the active interval; mid (amber) marks the element currently being compared against the target.

  1. Donald E. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, 2nd edition, 1998. ISBN 978-0-201-89685-5. ↩↩

  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, 4th edition, 2022. ISBN 978-0-262-04630-5. ↩↩↩

  3. Robert Sedgewick and Kevin Wayne. Algorithms. Addison-Wesley, 4th edition, 2011. ISBN 978-0-321-57351-3. ↩↩↩