vault

Binary Search

12 min read

Binary Search

Binary search finds a target value in a sorted array (or any monotone sequence) in O(log n) time by repeatedly halving the search space. It’s the canonical interview algorithm — simple in concept, vicious in off-by-one details, and shows up everywhere, including in problems where the “sorted array” is hidden inside the answer space rather than the input.

1. Intuition — The Phone Book

Imagine looking up “Smith” in a paper phone book.

  • You don’t start at page 1 and flip forward (that would be Linear Search — O(n)).
  • You open to roughly the middle. You see “Madison.” M < S, so the name is in the right half.
  • You open to roughly the middle of the right half. You see “Stevens.” S = S, so you’re in the right neighborhood — search a little around there.

Each look halves the remaining pages. A 1024-page book takes at most 10 looks (2¹⁰ = 1024). A million-page book takes 20. The number of steps grows very slowly — that’s logarithmic.

The crucial precondition: the data must be sorted (or otherwise monotone — see §8). On unsorted data, binary search returns nonsense.

2. The Worked Example (n = 10)

Find target = 23 in:

indices:   0   1   2   3   4   5   6   7   8   9
values:    2   5   8  12  16  23  38  56  72  91
Steplohimidarr[mid]Action
10941623 > 16, go right: lo = mid + 1 = 5
25975623 < 56, go left: hi = mid - 1 = 6
356523Found! Return 5

Three steps for n = 10. The general bound is ⌈log₂(n+1)⌉ ≈ 4 for n = 10 (we’re slightly under because we got lucky).

3. Pseudocode (Template 1: Find Exact Match)

binary_search(arr, target):
    lo := 0
    hi := length(arr) - 1
    while lo <= hi:
        mid := lo + (hi - lo) / 2          # integer division; avoids overflow
        if arr[mid] == target:
            return mid
        else if arr[mid] < target:
            lo := mid + 1
        else:
            hi := mid - 1
    return -1                               # not found

Why mid := lo + (hi - lo) / 2 and not (lo + hi) / 2? In languages with fixed-width integers (C, C++, Java), lo + hi can overflow if both are near INT_MAX. The reformulation avoids the overflow. Python’s arbitrary-precision integers don’t suffer from this, but always write the safe form — interviewers expect it. (See the famous Joshua Bloch Google Research blog post — JDK’s binary search had this bug for almost a decade.)

4. Python — Idiomatic, Iterative

def binary_search(arr: list[int], target: int) -> int:
    """Return index of target in sorted arr, or -1 if absent."""
    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

Python’s standard library exposes binary search via bisect:

import bisect
i = bisect.bisect_left(arr, target)   # leftmost insertion point
found = i < len(arr) and arr[i] == target

bisect_left returns the leftmost position where target could be inserted to keep the list sorted; bisect_right returns the rightmost. These are the foundations for the next two templates.

5. The Three Templates (THE Interview Topic)

A huge number of interview problems are “binary search but with a twist.” The twist is usually one of:

  1. Exact match — what we’ve covered above.
  2. Leftmost — first index where arr[i] >= target (a.k.a. lower bound).
  3. Rightmost — first index where arr[i] > target (a.k.a. upper bound).

These are not the same — and confusing them is the #1 source of off-by-one bugs.

Template 2: Leftmost (Lower Bound)

“Find the leftmost position where target could be inserted (or where it already exists).”

lower_bound(arr, target):
    lo := 0
    hi := length(arr)         # NOTE: not length - 1
    while lo < hi:            # NOTE: strict < not <=
        mid := lo + (hi - lo) / 2
        if arr[mid] < target:
            lo := mid + 1
        else:
            hi := mid          # NOTE: not mid - 1
    return lo

def lower_bound(arr, target):
    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

Why the boundary changes are the way they are:

  • hi = len(arr) (not len(arr) - 1) because the answer might be “insert at the very end.”
  • while lo < hi (strict, not <=) because the search space [lo, hi) is half-open — we exit when it has zero elements, not when lo crosses hi.
  • hi = mid (not mid - 1) because mid itself might be the answer (it satisfies arr[mid] >= target).

The half-open [lo, hi) invariant is the trick. Pick one convention and stick to it across the entire problem. Mixing closed [lo, hi] and half-open [lo, hi) mid-function is a guaranteed bug.

Template 3: Rightmost (Upper Bound)

“Find the leftmost position where target could be inserted after any existing copies.”

def upper_bound(arr, target):
    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

The only difference from lower_bound: <= instead of < in the comparison. That single character flip changes the semantics from ”≥ target” to ”> target.”

Counting occurrences. upper_bound(arr, x) - lower_bound(arr, x) = number of times x appears. Memorize this idiom — it shows up constantly.

6. The Loop Invariant Mental Model

The single most useful trick for getting binary search right is to state and maintain a loop invariant.

For Template 1 (closed interval [lo, hi]):

Invariant: if the target is in the array, it lies within arr[lo..hi] (inclusive).

For Templates 2/3 (half-open [lo, hi)):

Invariant: the answer (insertion point) lies within [lo, hi] — note hi is now exclusive in the search but the answer could be at lo or anywhere up to hi.

After each iteration, you must verify the invariant still holds. If arr[mid] < target and you set lo = mid + 1, you’ve ruled out arr[mid] as a possible answer — that’s only valid if arr[mid] truly cannot be the answer.

This sounds pedantic. It is. But after writing 100 binary searches, your fingers will produce the right pattern automatically and you’ll never need to invoke the invariant explicitly.

7. Complexity

  • Time: O(log n) — each iteration halves the search space, so the number of iterations is ⌈log₂ n⌉.
  • Space: O(1) iterative; O(log n) recursive (recursion stack).

The base of the logarithm doesn’t matter (see Big-O Notation §10.3).

Why log n is fast. For n = 10⁹, log₂ n ≈ 30. A linear scan would take a billion ops; binary search takes 30. That’s a ~33,000,000× speedup. Logarithmic is essentially free.

8. Binary Search on the Answer (Advanced — Very Common in Interviews)

This is the most-loved interview pattern: the input isn’t sorted, but the answer space is monotone.

Canonical example: “Capacity to Ship Packages Within D Days”

You have packages with given weights, must ship them in D days, packages must be loaded in order. What’s the minimum ship capacity?

Insight: if a capacity C works, every capacity C' > C also works. The set {C : C works} is a contiguous upper interval [answer, ∞). We binary-search for the boundary.

def ship_within_days(weights: list[int], days: int) -> int:
    def can_ship(capacity: int) -> bool:
        d, load = 1, 0
        for w in weights:
            if load + w > capacity:
                d += 1
                load = 0
            load += w
        return d <= days
 
    lo, hi = max(weights), sum(weights)   # the answer must be in this range
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_ship(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Two key skills here:

  1. Spotting that the answer space is monotone. Often the problem says “minimum X such that Y” or “maximum X such that Y” — that’s the giveaway.
  2. Writing a correct can_ship-style predicate. This is the actual algorithmic content; binary search just orchestrates it.

Other instances of “binary-search on answer”

  • “Smallest divisor given a threshold” — divide array values by d, binary-search on d
  • “Split array into k parts to minimize the largest sum”
  • “Minimum time to complete tasks given parallel workers”
  • “Median of two sorted arrays” — binary-search the partition point

The pattern: write a feasible(x: int) -> bool predicate that’s monotone in x, then binary-search for the boundary.

9. Variants Worth Knowing

9.1 Search in a Rotated Sorted Array

arr = [4, 5, 6, 7, 0, 1, 2] — sorted then rotated. Standard binary search fails (the array isn’t monotone).

Fix: at each mid, one of the two halves is still sorted (you can detect which by comparing arr[lo] and arr[mid]). Decide whether the target lies in the sorted half.

def search_rotated(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target: return mid
        if arr[lo] <= arr[mid]:           # left half sorted
            if arr[lo] <= target < arr[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                              # right half sorted
            if arr[mid] < target <= arr[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

9.2 Find Peak Element

arr where arr[i] != arr[i+1], find any local maximum. Binary search by direction-of-slope.

9.3 Search in a 2D Sorted Matrix

If rows and columns are sorted, treat the matrix as a 1D sorted array of length m × n and convert mid to (row, col). Or use the “staircase” search starting from top-right corner: O(m + n).

For an unbounded sorted sequence (no known length), repeatedly double the upper bound until you overshoot, then binary-search inside the bracket. Useful for searching in a stream-like structure.

For unimodal functions (single peak/valley), divide into thirds and discard the worse third. O(log n) but with a worse constant than binary search; rarely beats binary search even when applicable.

10. Common Interview Problems

ProblemPattern
Find first/last position of elementTemplates 2 & 3
Search insert positionTemplate 2
Find peak elementSlope-based
Median of two sorted arraysBinary search on partition
Capacity to ship in D daysBinary search on answer
Koko eating bananasBinary search on answer
Split array largest sumBinary search on answer
Search in rotated sorted arrayModified template
Find min in rotated sorted arrayModified template
sqrt(x) integerBinary search on answer (or Newton’s method)

11. Pitfalls (Read Carefully)

11.1 The Off-by-One Trifecta

Three independent decisions to keep consistent:

  • Interval style: closed [lo, hi] vs half-open [lo, hi)
  • Loop condition: lo <= hi for closed; lo < hi for half-open
  • Update rule: hi = mid - 1 for closed (we’ve ruled out mid); hi = mid for half-open (mid still possible)

Mix any two and you have a bug. Pick a convention and write it the same way every time.

11.2 Infinite Loops

If lo == hi and you never make lo strictly bigger or hi strictly smaller, you loop forever. Two common causes:

  • mid = (lo + hi) // 2 rounds toward lo, so hi = mid (not hi = mid - 1) is fine — but lo = mid is not, because mid == lo when hi - lo == 1. Always lo = mid + 1.
  • For “find rightmost,” some people use mid = (lo + hi + 1) // 2 (rounding up) to avoid the symmetric trap.

11.3 Integer Overflow

(lo + hi) / 2 overflows in 32-bit signed integers when lo + hi > 2³¹ - 1. Use lo + (hi - lo) / 2. Python is immune; the habit still matters for interviews and for portable code.

11.4 Searching Unsorted Data

Binary search on unsorted data returns garbage silently — no error. Make absolutely sure your input is sorted (or monotone in the relevant axis) before deploying binary search.

11.5 Comparing the Wrong Thing

When binary-searching on the answer, the predicate sometimes wraps complex logic (e.g., “can we ship within D days at capacity C?”). Make sure your predicate is truly monotone. If not, binary search will converge to nonsense.

11.6 Returning the Wrong Value

After exiting the loop, lo and hi typically point to near the answer but interpretation differs by template. After Template 1’s loop, lo is “smallest index with arr[i] >= target-ish” — but you should return -1 if no exact match. After Template 2’s loop, lo == hi is the lower bound. Print lo and hi after the loop and trace by hand on the smallest non-trivial example before submitting.

12. Diagram — How the Window Shrinks

flowchart TD
    subgraph "Iteration 1"
        A1["[lo=0, hi=9] mid=4"]
    end
    subgraph "Iteration 2"
        A2["[lo=5, hi=9] mid=7"]
    end
    subgraph "Iteration 3"
        A3["[lo=5, hi=6] mid=5 ✓"]
    end
    A1 -->|"arr[mid]<target"| A2
    A2 -->|"arr[mid]>target"| A3

What this diagram shows. Three iterations of binary search on the n=10 example from §2. After each comparison, exactly half of the remaining window is discarded. The O(log n) complexity is exactly the number of times you can halve n before it reaches 1.

13. Open Questions

  • Is there a clean way to teach the half-open vs closed interval distinction without rote memorization? Various texts pick one convention; CLRS uses half-open, Sedgewick uses closed.
  • When does ternary search beat binary search in practice? Almost never for sorted-array search; sometimes for continuous unimodal-function optimization.

14. See Also

Graph View

Backlinks