Binary Search

The Power of Halving

In the early days of printed phone directories, a party trick among mathematicians was to find any name in a 1,000-page phonebook in at most 10 steps. The trick: open to page 500 and check whether the target name is alphabetically before or after that page. Then open to page 250 or 750 depending on the answer. Repeat. In 10 halvings, $2^{10} = 1024$ — you can cover every page in a 1,000-page book.

This is binary search: one of the oldest, most elegant, and most frequently misimplemented algorithms in computer science. It is deceptively simple to describe and surprisingly tricky to implement correctly. Jon Bentley, author of "Programming Pearls," famously reported that after assigning binary search as an exercise to professional programmers, roughly 90% produced an incorrect implementation. Dijkstra himself noted that the first correct published proof of binary search appeared only 16 years after the algorithm was first described.

The bugs cluster around one place: the exact handling of the boundary conditions. Off-by-one errors are the nemesis of binary search. This chapter will give you a framework for thinking about binary search that makes the correct boundary conditions obvious, and show you the full range of problems where binary search applies — far beyond simple value lookup.

Concept Explanation

Binary search is an algorithm that finds a target in a sorted collection by repeatedly halving the search space. It compares the target to the middle element; if they match, the search is done. If the target is smaller, search the left half; if larger, search the right half.

The core insight: Binary search works on any monotonic predicate — any condition that transitions from False to True (or True to False) exactly once across the sorted domain. This generalization is far more powerful than "find a value in a sorted array."

Think of binary search like guessing a number between 1 and 1,000,000. If you guess 500,000 and your opponent says "higher," you have eliminated half of all possibilities with one guess. In 20 guesses ( $2^{20} = 1,048,576$ ), you can find any number. Compare this to guessing 1, then 2, then 3 — that would take up to a million guesses. The difference is $O(\log n)$ vs $O(n)$ .

Key requirement: The input must be sorted (or more generally, must satisfy a monotonic property). Without this guarantee, binary search produces incorrect results. This requirement is the source of many bugs: engineers apply binary search to data that is not fully sorted.

Template: The most bug-resistant way to think about binary search is to maintain the invariant: the answer is always within [low, high]. The loop continues while low < high (not <=), and you carefully shrink the range without ever excluding the potential answer.

Mathematical Foundation

Number of iterations for an array of size $n$ :

$\text{iterations} = \lceil \log_2 n \rceil$

For $n = 10^9$ (1 billion), that is only 30 iterations. This is the power of logarithmic growth.

Recurrence relation: Binary search divides the problem in half each step:

$T(n) = T\left(\frac{n}{2}\right) + O(1) \implies T(n) = O(\log n)$

By the Master Theorem: $a=1, b=2, d=0$ . Since $\log_2 1 = 0 = d$ , we get $T(n) = O(n^0 \log n) = O(\log n)$ .

Space complexity:

Iterative binary search: $O(1)$ — only a few pointers.
Recursive binary search: $O(\log n)$ — call stack depth equals number of iterations.

Why $\lfloor mid \rfloor$ not $\lceil mid \rceil$ matters:

If low = 0, high = 1 and mid = (0 + 1) // 2 = 0 (floor), and the wrong branch sets low = mid, then low never advances — infinite loop. The choice of rounding direction must be consistent with how you update low and high.

Integer overflow prevention: In languages with fixed-size integers:

$\text{naive: } mid = (low + high) / 2 \quad \text{can overflow if } low + high > \text{INT\_MAX}$

$\text{safe: } mid = low + (high - low) / 2$

Python integers are arbitrary precision, so overflow is not a concern in Python.

Algorithm / Logic

Standard binary search — step by step:

Set low = 0, high = len(arr) - 1.
While low <= high: a. Compute mid = low + (high - low) // 2. b. If arr[mid] == target, return mid. c. If arr[mid] < target, set low = mid + 1 (eliminate left half including mid). d. If arr[mid] > target, set high = mid - 1 (eliminate right half including mid).
Return -1 (not found).

Find first occurrence (leftmost) — step by step:

Set low = 0, high = len(arr) - 1, result = -1.
While low <= high: a. Compute mid. b. If arr[mid] == target: save result = mid, then set high = mid - 1 (keep searching left). c. If arr[mid] < target: set low = mid + 1. d. If arr[mid] > target: set high = mid - 1.
Return result.

BINARY_SEARCH(arr, target):
  low = 0
  high = len(arr) - 1
  while low <= high:
    mid = low + (high - low) // 2
    if arr[mid] == target:
      return mid
    elif arr[mid] < target:
      low = mid + 1
    else:
      high = mid - 1
  return -1

LOWER_BOUND(arr, target):
  // Returns index of first element >= target
  low = 0
  high = len(arr)
  while low < high:
    mid = low + (high - low) // 2
    if arr[mid] < target:
      low = mid + 1
    else:
      high = mid
  return low

Programming Implementation

Python — binary search and all major variants:

from typing import List, Optional
import bisect


# ── Standard binary search ────────────────────────────────────────────────────

def binary_search(arr: List[int], target: int) -> int:
    """O(log n) — returns index of target, or -1 if not found."""
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1


# ── First and last occurrence ─────────────────────────────────────────────────

def first_occurrence(arr: List[int], target: int) -> int:
    """O(log n) — leftmost index of target in arr with duplicates."""
    low, high, result = 0, len(arr) - 1, -1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            result = mid
            high = mid - 1   # keep searching left for earlier occurrence
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result


def last_occurrence(arr: List[int], target: int) -> int:
    """O(log n) — rightmost index of target in arr with duplicates."""
    low, high, result = 0, len(arr) - 1, -1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            result = mid
            low = mid + 1    # keep searching right
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result


def count_occurrences(arr: List[int], target: int) -> int:
    """O(log n) — count how many times target appears."""
    first = first_occurrence(arr, target)
    if first == -1:
        return 0
    return last_occurrence(arr, target) - first + 1


# ── Rotated sorted array ──────────────────────────────────────────────────────

def search_rotated(arr: List[int], target: int) -> int:
    """
    O(log n) — search in a sorted array that has been rotated.
    Example: [4, 5, 6, 7, 0, 1, 2] was [0, 1, 2, 4, 5, 6, 7].
    Key insight: at least one half of the array is always sorted.
    """
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            return mid
        # Left half is sorted
        if arr[low] <= arr[mid]:
            if arr[low] <= target < arr[mid]:
                high = mid - 1
            else:
                low = mid + 1
        # Right half is sorted
        else:
            if arr[mid] < target <= arr[high]:
                low = mid + 1
            else:
                high = mid - 1
    return -1


# ── Binary search on answer (generalization) ──────────────────────────────────

def minimum_pages_per_day(pages: List[int], days: int) -> int:
    """
    O(n log(sum)) — find minimum reading speed to finish 'pages' in 'days'.
    Classic 'binary search on the answer' pattern.
    The predicate: 'can we finish at speed k?' is monotonic.
    """
    def can_finish(speed: int) -> bool:
        """Can we read all books at given pages/day in the allowed days?"""
        days_needed = sum((p + speed - 1) // speed for p in pages)
        return days_needed <= days

    low, high = max(pages), sum(pages)  # min possible, max possible speed
    while low < high:
        mid = low + (high - low) // 2
        if can_finish(mid):
            high = mid       # mid works; try smaller
        else:
            low = mid + 1    # mid doesn't work; try larger
    return low


def koko_eating_bananas(piles: List[int], h: int) -> int:
    """
    O(n log(max_pile)) — find minimum eating speed.
    Same pattern: binary search on the answer space.
    """
    def can_eat_all(speed: int) -> bool:
        return sum((pile + speed - 1) // speed for pile in piles) <= h

    low, high = 1, max(piles)
    while low < high:
        mid = low + (high - low) // 2
        if can_eat_all(mid):
            high = mid
        else:
            low = mid + 1
    return low


# ── Using Python's bisect module ──────────────────────────────────────────────

def using_bisect(arr: List[int], target: int) -> int:
    """Use Python's built-in bisect for lower/upper bound."""
    idx = bisect.bisect_left(arr, target)
    if idx < len(arr) and arr[idx] == target:
        return idx
    return -1


def find_insert_position(arr: List[int], target: int) -> int:
    """O(log n) — where to insert target to keep arr sorted."""
    return bisect.bisect_left(arr, target)

JavaScript — binary search for frontend and backend:

function binarySearch(arr, target) {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

// Binary search on answer: find minimum capacity for ship weight
function shipWithinDays(weights, days) {
  const canShip = (capacity) => {
    let daysNeeded = 1, current = 0;
    for (const w of weights) {
      if (current + w > capacity) { daysNeeded++; current = 0; }
      current += w;
    }
    return daysNeeded <= days;
  };

  let low = Math.max(...weights);
  let high = weights.reduce((a, b) => a + b, 0);
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (canShip(mid)) high = mid;
    else low = mid + 1;
  }
  return low;
}

System Design Perspective

Binary search underpins many system components:

[Search Query: "find product price between $10-$50"]
          ↓
[API Server]
          ↓
[Database Query Planner]
  — B-Tree index: binary search to find first key ≥ $10 (lower bound)
  — Scan forward until key > $50 (upper bound)
  — O(log n + k) where k = result set size
          ↓
[Cache Layer (Redis sorted sets)]
  — ZRANGEBYSCORE: internally uses skip list (O(log n))
  — Equivalent of binary search on sorted score set
          ↓
[Search Engine (Elasticsearch)]
  — Inverted index lookup: binary search in sorted posting lists
  — Merge posting lists for multi-term queries

Real company applications:

PostgreSQL and MySQL: B-tree indexes use binary search at each node to find the correct child pointer — $O(\log n)$ lookups even on tables with billions of rows.
Git bisect: Git's bisect command uses binary search on the commit history to find the exact commit that introduced a bug — given a "good" commit and a "bad" commit, it repeatedly checks the midpoint.
Game engines: Binary search is used for collision detection (finding which spatial partition a point falls into), animation blending (finding the right keyframe), and asset loading (sorted asset tables).
CDN cache invalidation: Akamai and Cloudflare use binary search on sorted cache timestamps to find expired entries efficiently.

Visual Content Suggestions

Binary search step-by-step animation: Array with highlighted low, mid, high pointers narrowing down on a target value.
Comparison: linear search vs binary search: Two timelines showing $O(n)$ vs $O(\log n)$ steps for $n = 1000$ .
Rotated array diagram: Annotated array showing the rotation point and how the algorithm decides which half to search.
Binary search on answer space: Number line from low to high with the predicate boundary marked.
B-tree index structure: Tree nodes with binary search annotations at each level.

Real-World Examples

Google's Bigtable: Rows are stored in sorted order by row key. Finding a row uses binary search on a hierarchical index (SSTable index → data block). This enables $O(\log n)$ row lookups across petabytes of data distributed across thousands of servers.

Netflix's AB testing: Netflix stores experiment configurations as sorted arrays indexed by user ID ranges. When a user logs in, binary search on the sorted ranges determines which experiment variant they are assigned to — $O(\log k)$ where $k$ is the number of active experiments.

Amazon's catalog search: Price range filtering in product search uses binary search on indexed price columns to find the lower and upper bounds, then scans only the qualifying rows. This turns a potential $O(n)$ scan into $O(\log n + k)$ where $k$ is the result count.

Meta's News Feed ranking: After scoring candidate posts, the feed is assembled using a binary search to find the insertion point for each post in the ranked list, maintaining a sorted order without re-sorting the entire feed each time.

Common Mistakes

Mistake 1: Off-by-one in boundary updates. The most common binary search bug. Setting high = mid vs high = mid - 1 (or low = mid vs low = mid + 1) determines whether you include or exclude mid in the next iteration. The rule: if arr[mid] is definitely not the answer, use mid - 1 or mid + 1. If it could be the answer (e.g., finding the first element satisfying a condition), keep it in the range.

Mistake 2: Infinite loop when low = high - 1. If low = 2, high = 3, and mid = 2 (floor), and you set low = mid (not mid + 1), then low stays at 2 forever. Always use low = mid + 1 when you are moving the lower bound up, ensuring the range strictly shrinks.

Mistake 3: Applying binary search to unsorted data. Binary search silently returns wrong answers on unsorted data — it terminates without finding the target even when the target is present. Always verify the sort invariant before applying binary search.

Mistake 4: Integer overflow in other languages. (low + high) / 2 overflows in Java/C++ for large values. Always use low + (high - low) / 2. Python avoids this because integers are arbitrary precision, but good habit.

Mistake 5: Not recognizing binary search on the answer space. Many problems — "find minimum X such that condition Y holds" — are binary search problems in disguise. The key: if condition Y is monotonic (once true, always true for larger X), binary search on the answer space. Practice recognizing this pattern; it unlocks a large class of hard problems.

Interview Angle

Q: How do you find the first and last position of a target in a sorted array with duplicates?

A: Run binary search twice. For the first position, when you find the target at index mid, save it and continue searching left by setting high = mid - 1. For the last position, when you find the target, save it and continue searching right by setting low = mid + 1. Both runs are $O(\log n)$ , giving $O(\log n)$ total. This is preferable to finding any occurrence and then linearly scanning left and right, which degrades to $O(n)$ if all elements are the same. In Python, you can use bisect.bisect_left(arr, target) and bisect.bisect_right(arr, target) - 1 for the same effect.

Q: You need to find the square root of an integer n, truncated to an integer. How do you do it efficiently?

A: Binary search on the answer space from 0 to $n$ . For each candidate mid, check if mid * mid <= n. We want the largest mid where this is true. Set low = 0, high = n. When mid * mid <= n, this mid is a candidate — save it and search right (low = mid + 1). When mid * mid > n, search left (high = mid - 1). This runs in $O(\log n)$ time and $O(1)$ space. For n = 10^9, only 30 iterations. This pattern — binary search on integers to find the boundary of a monotonic predicate — is the generalized template that solves dozens of "find the minimum/maximum satisfying X" problems.

Summary

Binary search finds a target in a sorted collection in $O(\log n)$ time by halving the search space each iteration.
The algorithm requires the input to be sorted (or satisfy a monotonic property) — the most common source of binary search bugs.
Three critical implementation details: computing mid without overflow (low + (high - low) // 2), updating low/high correctly, and handling the termination condition.
Variants: first occurrence, last occurrence, lower bound, upper bound — each requires a subtle change to the update logic.
Binary search on the answer space is the key generalization: for any "find minimum X satisfying Y" problem where Y is monotonic, binary search on X in $O(\log(\text{range}) \cdot \text{check time})$ .
Python's bisect module provides bisect_left (lower bound) and bisect_right (upper bound) as $O(\log n)$ built-ins.
Database B-tree indexes are built on binary search principles, enabling $O(\log n)$ lookups on billion-row tables.
Git's bisect command is binary search applied to commit history for bug finding.
Iterative implementation is preferred over recursive to avoid $O(\log n)$ stack overhead.
Off-by-one errors cluster around low <= high vs low < high and mid ± 1 updates — use the template that matches your predicate definition.

LeetCode Practice

Drill the concepts from this chapter with these curated problems:

#	Problem	Difficulty	Pattern
704	Binary Search	🟢 Easy	The template — get the boundary conditions right here first
278	First Bad Version	🟢 Easy	Binary search on a predicate (first True in a False...True sequence)
35	Search Insert Position	🟢 Easy	Lower bound / `bisect_left` pattern
33	Search in Rotated Sorted Array	🟡 Medium	Binary search on a non-uniformly sorted array
153	Find Minimum in Rotated Sorted Array	🟡 Medium	Identifying which half is sorted
875	Koko Eating Bananas	🟡 Medium	Binary search on the answer space — the key generalization
1011	Capacity to Ship Packages Within D Days	🟡 Medium	"Find minimum X satisfying Y" pattern
4	Median of Two Sorted Arrays	🔴 Hard	Binary search on partition index — O(log(min(m,n)))