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.

Complexity

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.

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

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.

← Back to Algorithms