Binary search: finding quickly in sorted data

In short: Binary search halves the search range of a sorted list at each step and thus needs only a logarithmic number of comparisons instead of a linear number.

In more detail: Like guessing a number between 1 and 100 (“higher/lower?”): always look at the middle, then discard the wrong half. Prerequisite: the data is sorted and access to any position is fast (array).

In Depth

Idea and procedure

1. left = 0, right = n − 1.
2. mid = left + (right − left) / 2.
3. If a[mid] == target → found. If a[mid] < target → left = mid + 1, else right = mid − 1.
4. Repeat until left > right (not found). Example: search 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]: middle 16 < 23 → right half; middle 56 > 23 → left; middle 23 → found after 3 steps.

Code

def binary_search(a, target):
    left, right = 0, len(a) - 1
    while left <= right:
        mid = left + (right - left) // 2   # avoids overflow
        if a[mid] == target:
            return mid
        if a[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

In Python: module bisect (bisect_left), in Java Arrays.binarySearch, JavaScript manually, C++ std::binary_search/lower_bound. Typical errors: off-by-one at the bounds, overflow with (l + r) / 2 in fixed integer types, infinite loops through wrong bound changes, unsorted data.

Running time

At each step the range halves: at most ⌈log₂ n⌉ + 1 comparisons. 1 million entries: ≈ 20 comparisons; 1 billion: ≈ 30. Linear search needs on average n/2. Effort: O(log n). But: sorting costs O(n log n); worthwhile if searched often. With linked lists binary search brings nothing (no direct access), instead search trees/B-trees/indexes.

Variants and applications

• Lower/upper bound (first/last position of a value, insertion position).
• Binary search on the answer: “smallest capacity such that delivery works in 5 days” (use monotonicity).
• Root/zero (bisection method).
• git bisect: finds the faulty commit in log₂(n) steps.
• Database indexes, phone book, dictionary, sorted files, autocomplete.
• Exam tip (IHK): derive the number of steps for n elements (2^k ≥ n).

See also: Big-O notation, Sorting, B-tree