Binary Search

Binary search finds a target in a sorted sequence by repeatedly halving the search range. O(log n) — the canonical "divide-and-conquer" example, and the basis for bisect in Python's standard library.

1. Overview

Binary search is the standard example of how ordering data buys speed. Each comparison with the middle element eliminates half of the remaining candidates, so the number of comparisons grows with the logarithm of the input size. Doubling the array adds only one comparison. Searching a billion sorted values takes at most 30 comparisons, while a linear scan could need a billion. The price is the precondition: the data must be sorted by the same ordering you search with, and it must support constant-time access by index.

2. Complexity

3. How it works

Maintain lo and hi indices. Compute mid = (lo + hi) // 2. If arr[mid] == target, return mid; if it's smaller, set lo = mid + 1; else hi = mid - 1. Repeat until lo > hi. Each step halves the range, giving log₂ n iterations.

4. Python implementation

def binary_search(arr, target):
    """Iterative binary search — returns index or -1."""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


print(binary_search([1, 3, 5, 7, 9, 11, 13], 7))   # 3
print(binary_search([1, 3, 5, 7, 9, 11, 13], 4))   # -1


# In production: use bisect.
import bisect
arr = [1, 3, 5, 7, 9, 11, 13]
i = bisect.bisect_left(arr, 7)
print(i, arr[i] == 7)   # 3 True

5. Trade-offs

• O(log n) — drastically faster than linear search for sorted input.
• Requires the sequence to be sorted (and randomly indexable, e.g. an array, not a linked list).
• Off-by-one bugs in hand-rolled implementations are notoriously common; use bisect.
• Variants: bisect_left / bisect_right for first/last occurrence in duplicates.

6. Step-by-Step Trace

Each row shows the live range [lo, hi] in normal cells, the midpoint highlighted in yellow, and discarded cells greyed out. The loop invariant is: if the target exists, its index lies inside [lo, hi]. Every branch either returns or strictly shrinks the range, so the loop terminates. When lo > hi the range is empty and the target is absent.

7. Lower and Upper Bound Variants

Real problems rarely ask "is x present?" They ask "where is the first element that is at least x?" (lower bound), or "where would x be inserted to keep order?" Writing the search over a half-open range [lo, hi) handles duplicates and insertion points uniformly:

def lower_bound(arr, x):
    """First index i with arr[i] >= x (len(arr) if none)."""
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

def upper_bound(arr, x):
    """First index i with arr[i] > x."""
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo

a = [1, 2, 4, 4, 4, 7]
print(lower_bound(a, 4), upper_bound(a, 4))   # 2 5  -> three 4s
print(upper_bound(a, 4) - lower_bound(a, 4))  # count of 4s = 3

These match bisect.bisect_left and bisect.bisect_right. The same template also implements binary search on the answer: when a predicate is false for small values and true for large ones (for example "can all packages ship within D days with capacity C?"), search the smallest C for which it is true. Python 3.10+ bisect functions accept a key argument for searching records by a field.

8. When to Use It

9. Pitfalls

• Mixing closed [lo, hi] and half-open [lo, hi) conventions in one function is the source of most infinite loops and off-by-one errors.
• In fixed-width integer languages, (lo + hi) / 2 can overflow; use lo + (hi - lo) / 2. Python integers do not overflow.
• Searching data sorted by a different key or comparator than the one you compare with.
• Applying binary search to a linked list: finding the middle is O(n), so nothing is gained.

10. Complexity in Detail

The iterative version uses constant extra space; a recursive version uses one stack frame per halving, which is still only about 30 frames for a billion elements. If the array must first be sorted, add O(n log n) once; this is amortised away after roughly log n lookups compared with repeated linear scans. On modern hardware the constant factors matter too: for very small arrays, a linear scan can beat binary search because it is branch-predictable and reads memory sequentially, which is why some libraries switch to a linear scan below a small threshold. For huge sorted arrays, cache misses dominate, and layouts such as the Eytzinger (BFS-order) layout or B-tree style blocks reduce them.

Recursive form

def bsearch(arr, x, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == x:
        return mid
    if arr[mid] < x:
        return bsearch(arr, x, mid + 1, hi)
    return bsearch(arr, x, lo, mid - 1)

The recursive form mirrors the divide-and-conquer description directly, which makes it easy to reason about, but the iterative form is preferred in Python because it avoids call overhead and the recursion limit.

11. Related Topics

• Linear Search
• Searching overview
• Sorting algorithms
• Red-Black Tree

← Back to Algorithms

Featured Videos