Binary Search - The Efficient Halving Algorithm

Binary Search is one of the most fundamental and efficient searching algorithms in computer science. It is built on the divide-and-conquer principle: instead of scanning every element one by one, it repeatedly cuts the search space in half, homing in on the target with remarkable speed. The one non-negotiable requirement is that the data must be sorted — binary search simply cannot work on an unsorted collection.

History

The concept of binary search is older than computers themselves. Its formal description as a computer algorithm is credited to John Mauchly, who outlined it in 1946 as part of early work on algorithm design. However, the algorithm Mauchly described had subtle off-by-one bugs that plagued implementations for years. It wasn’t until 1960 that Derrick Henry Lehmer published the clean, correct iterative form that programmers rely on today. Despite its apparent simplicity, a 2006 study found that the majority of published binary search implementations contained at least one bug — a testament to how tricky getting the boundary conditions exactly right can be.

How It Works

Binary search maintains two pointers — a left boundary and a right boundary — that define the portion of the array still under consideration. On each iteration, it calculates the midpoint and compares the element there against the target:

1. Initialise: Set left = 0 and right = length - 1.
2. Find the midpoint: Compute mid = left + (right - left) / 2 (using this form avoids integer overflow).
3. Compare: If array[mid] equals the target, the search is done — return mid.
4. Eliminate the left half: If the target is greater than array[mid], set left = mid + 1 and repeat.
5. Eliminate the right half: If the target is less than array[mid], set right = mid - 1 and repeat.
6. Not found: If left exceeds right, the target is not in the array — return -1.

Each iteration discards exactly half of the remaining candidates, which is what gives the algorithm its logarithmic character. For an array of one million elements, binary search needs at most twenty comparisons to locate any element — or confirm it is absent.

Time Complexity

Binary search achieves a time complexity of $O(\log n)$ in the average and worst cases. Every comparison halves the search space, so the maximum number of steps needed is proportional to the logarithm (base 2) of the input size.

In the best case — when the very first midpoint happens to be the target — the algorithm terminates in $O(1)$ time. This is a lucky coincidence rather than something you can count on, so the complexity that matters in practice is $O(\log n)$.

Case	Complexity
Best	$O(1)$
Average	$O(\log n)$
Worst	$O(\log n)$

Space Complexity

The iterative version of binary search runs in $O(1)$ space — it only needs a handful of variables (left, right, mid) regardless of input size.

A recursive implementation, while elegant, pays a price: each recursive call adds a frame to the call stack, and the stack can grow up to $\log n$ frames deep before unwinding. This gives the recursive version an $O(\log n)$ space complexity. For most practical purposes, the iterative form is preferred precisely because it avoids this overhead.

Advantages and Disadvantages

Advantages:

• Extremely fast at $O(\log n)$ — far superior to linear search’s $O(n)$ for large datasets.
• Constant $O(1)$ space usage in its iterative form.
• Simple to implement once the boundary conditions are understood.
• Works well as a building block inside more complex algorithms (e.g., finding insertion points, range queries).

Disadvantages:

• Requires a sorted array. If the data is not sorted, binary search produces incorrect results. Pre-sorting costs $O(n \log n)$, which may outweigh the benefit for one-off searches.
• Only applicable to random-access data structures. It cannot be used directly on linked lists, where computing the midpoint costs $O(n)$.
• Overkill for very small arrays — a plain linear scan is simpler and has negligible overhead when $n$ is tiny.

When to Use Binary Search

Binary search is the right tool whenever:

• The data is sorted and changes infrequently. If you sort once and search many times, the upfront cost is quickly recovered.
• You need fast repeated lookups. Each search costs $O(\log n)$, making it ideal for large, stable datasets such as dictionaries, phone books, or indexed database columns.
• You’re working with random-access collections. Arrays and array-backed structures (like std::vector or a Python list) are a natural fit.
• You need to find boundaries. Variants like lower bound and upper bound binary search are indispensable for range queries, finding the first or last occurrence of a value, or determining where to insert an element to keep an array sorted.

In conclusion, binary search is a deceptively simple algorithm with profound practical impact. Its $O(\log n)$ performance makes it one of the first tools to reach for when querying sorted data — just remember to ensure that sorted precondition is satisfied before you start.