Binary search explained: how it works, code and complexity

What problem binary search solves

Linear search checks items one by one and needs up to n comparisons. If the data is sorted, you can do much better: compare the target with the middle item, and you immediately know which half to keep. This is the same idea as looking up a word in a paper dictionary.

Binary search also works on anything that is monotonic, not only arrays. If a yes/no condition is false for all small values and true for all large ones, binary search finds the boundary. This is called binary search on the answer.

Worked example, step by step

Search for 23 in the sorted list [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indexes 0 to 9). Keep two indexes, lo and hi, that bound the range still to be checked.

Three comparisons instead of six for a linear scan. For a list of a million items, binary search needs at most 20.

Python implementation

The iterative version below uses a closed range [lo, hi]: both ends are still candidates. The loop runs while the range is not empty.

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1          # target is in the right half
        else:
            hi = mid - 1          # target is in the left half
    return -1                     # not found
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(data, 23))   # 5
print(binary_search(data, 7))    # -1

In real Python code, use the standard library module bisect. bisect_left returns the leftmost position where the target could be inserted while keeping the list sorted, which also tells you whether it is present.

from bisect import bisect_left, bisect_right, insort
data = [1, 3, 3, 3, 7, 9]
i = bisect_left(data, 3)
print(i, bisect_right(data, 3))   # 1 4  (3 occupies indexes 1..3)
print(i < len(data) and data[i] == 3)   # True: 3 is present
print(bisect_left(data, 5))       # 4: insertion point for 5
insort(data, 5)
print(data)                       # [1, 3, 3, 3, 5, 7, 9]

Time and space complexity

Variants: first, last and binary search on the answer

Many problems ask not whether a value exists but where a boundary is: the first index with a value at least x, the last occurrence of x, or the smallest number that satisfies a condition. Use a half-open range [lo, hi) and never stop early.

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi) with ok(x) True, or hi if none.
    ok must be False...False True...True over the range."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid          # mid may be the answer, keep it
        else:
            lo = mid + 1      # mid is too small
    return lo
data = [1, 3, 3, 3, 7, 9]
print(first_true(0, len(data), lambda i: data[i] >= 3))   # 1
# Integer square root of 200: largest x with x*x <= 200
print(first_true(0, 201, lambda x: x * x > 200) - 1)      # 14

• Lower bound (first index with value ≥ x): bisect_left.
• Upper bound (first index with value > x): bisect_right.
• Count of x in a sorted list: bisect_right(a, x) - bisect_left(a, x).
• Search in a rotated sorted array, peak finding and minimizing a maximum (for example, the smallest capacity that ships all packages in D days) are classic interview variants.

Common mistakes

• Mixing range conventions. With a closed range use lo <= hi and hi = mid - 1; with a half-open range use lo < hi and hi = mid. Mixing them causes infinite loops or skipped elements.
• Writing lo = mid instead of lo = mid + 1. When hi = lo + 1, mid equals lo and the loop never ends.
• Running binary search on unsorted data. It returns wrong answers without any error.
• Integer overflow in (lo + hi) / 2 in languages with fixed-size integers such as Java, C and C++. Use lo + (hi - lo) / 2. Python integers do not overflow, so (lo + hi) // 2 is safe.
• Returning the first match found when the task asks for the first occurrence among duplicates.

When to use binary search

Real-world uses include database and file-system indexes (B-trees generalize the idea), git bisect for finding the commit that introduced a bug, looking up a value in a sorted table of ranges such as IP blocks, and many numeric problems where you search for a threshold.