## Introduction Binary search is one of the most fundamental algorithms in computer science. Despite its simplicity, it is surprisingly easy to get wrong — and its variants power everything from database indexing to machine learning hyperparameter tuning. The algorithm was first published by John Mauchly in 1946, but the first bug-free implementation didn't appear until 1962 . As Knuth famously documented, even experienced programmers frequently introduce off-by-one errors in their binary search implementations . In this article we will build up from the basic algorithm to several powerful variants. We start with the classic algorithm, explore its tree interpretation (see ), and then move to advanced patterns like search-on-answer. ## The Classic Algorithm Given a sorted array $A$ of $n$ elements, binary search finds whether a target value $t$ exists in $O(\log n)$ time . ```python def binary_search(arr: list[int], target: int) -> int: lo, hi = 0, len(arr) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if arr[mid] == target: return mid elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1 ``` The key insight is that each comparison eliminates half of the remaining search space, giving us logarithmic time complexity. This can be visualized as a decision tree where each node represents a comparison:

As shown in , each comparison at a node eliminates an entire subtree, halving the remaining candidates. The maximum number of comparisons is $\lceil \log_2(n+1) \rceil$. ## Variant 1: Lower Bound The **lower bound** variant finds the first position where an element is _greater than or equal to_ the target. This is equivalent to C++'s `std::lower_bound`. ```python def lower_bound(arr: list[int], target: int) -> int: lo, hi = 0, len(arr) while lo < hi: mid = lo + (hi - lo) // 2 if arr[mid] < target: lo = mid + 1 else: hi = mid return lo ``` Always use `lo + (hi - lo) // 2` instead of `(lo + hi) // 2`. In languages with fixed-width integers (C, Java), the latter can overflow when `lo + hi` exceeds `INT_MAX`. ```system-verilog // 4-bit Counter in SystemVerilog module counter_4bit ( input logic clk, // Clock input input logic reset_n, // Asynchronous reset (active low) output logic [3:0] q // 4-bit output ); // Sequential logic block always_ff @(posedge clk or negedge reset_n) begin if (!reset_n) begin q <= 4'b0000; // Reset the counter to zero end else begin q <= q + 1'b1; // Increment the counter end end endmodule ``` ```vhdl -- 4-bit Counter in VHDL library ieee; use ieee.std_logic_1164.all; use ieee.numeric_std.all; entity counter_4bit is port ( clk : in std_logic; reset_n : in std_logic; q : out std_logic_vector(3 downto 0) ); end entity counter_4bit; architecture behavioral of counter_4bit is signal r_count : unsigned(3 downto 0); begin process(clk, reset_n) begin if reset_n = '0' then r_count <= (others => '0'); elsif rising_edge(clk) then r_count <= r_count + 1; end if; end process; -- Convert unsigned internal signal back to std_logic_vector for the port q <= std_logic_vector(r_count); end architecture behavioral; ``` ## Variant 2: Search on Answer Sometimes the search space is not an array but a range of possible answers. We binary-search on a **monotonic predicate** — a function $f(x)$ that flips from `false` to `true` at some threshold. $$ f(x) = \begin{cases} \text{false} & x < x^* \\ \text{true} & x \geq x^* \end{cases} $$ The monotonic predicate in is the foundation of the search-on-answer technique. lists common problems that reduce to this pattern. | Problem | Predicate | | --------------------------------------------- | ------------------------------------------------------------ | | Minimum capacity to ship packages in $D$ days | Can we ship all packages with capacity $x$ in $\leq D$ days? | | Kth smallest element in a matrix | Are there $\geq k$ elements $\leq x$ in the matrix? | | Allocate minimum pages | Can we allocate all books such that max pages $\leq x$? | This technique extends binary search beyond arrays into continuous and discrete optimization. Bentley's work on multidimensional search trees generalized many of these ideas to higher dimensions. ## Complexity Analysis | Variant | Time | Space | | ----------------- | ------------------- | ------ | | Classic | $O(\log n)$ | $O(1)$ | | Lower/Upper bound | $O(\log n)$ | $O(1)$ | | Search on answer | $O(\log R \cdot C)$ | $O(1)$ | As shown in , all variants maintain $O(1)$ space complexity. The time complexity for search-on-answer depends on the range $R$ of the answer space and the cost $C$ of evaluating the predicate. ## Algorithm Flowchart The following diagram illustrates the control flow of the classic binary search algorithm: ```tikz caption="Flowchart of the classic binary search algorithm." id="fig:flowchart" \begin{tikzpicture}[ startstop/.style={rectangle, rounded corners, minimum width=3cm, minimum height=1cm, text centered, draw=white, fill=red!20, text=black}, process/.style={rectangle, minimum width=3cm, minimum height=1cm, text centered, draw=white, fill=blue!20, text=black}, decision/.style={diamond, minimum width=3cm, minimum height=1cm, text centered, draw=white, fill=green!20, text=black}, arrow/.style={thick, ->, >=Stealth, white} ] \node (start) [startstop] {Start}; \node (init) [process, below of=start, yshift=-0.8cm] {$lo \gets 0,\ hi \gets n-1$}; \node (check) [decision, below of=init, yshift=-1.2cm] {$lo \leq hi$?}; \node (mid) [process, below of=check, yshift=-1.2cm] {$mid \gets lo + \lfloor(hi-lo)/2\rfloor$}; \node (found) [startstop, below of=mid, yshift=-1.2cm] {Return $mid$}; \node (notfound) [startstop, right of=check, xshift=3.5cm] {Return $-1$}; \draw [arrow] (start) -- (init); \draw [arrow] (init) -- (check); \draw [arrow] (check) -- node[anchor=east, text=white] {yes} (mid); \draw [arrow] (check) -- node[anchor=south, text=white] {no} (notfound); \draw [arrow] (mid) -- (found); \end{tikzpicture} ``` As shown in , the algorithm repeatedly halves the search space until the target is found or the bounds cross. ## Key Takeaways 1. Always use `lo + (hi - lo) // 2` instead of `(lo + hi) // 2` to avoid integer overflow. 2. Be precise about loop invariants — most binary search bugs come from off-by-one errors in the bounds. 3. The "search on answer" pattern is the most versatile variant and appears in a huge number of problems. 4. Binary search can be visualized as a BST traversal (), which helps build intuition about its logarithmic behavior. In the next article, we will explore graph traversal algorithms and their applications.

Algorithms