🧩 Data Structures & Algorithms · Chapter 10

Binary search

A million sorted items, and you can find any one in 20 looks. The catch: get one +1 wrong and it loops forever.

Study this lesson free in the app →

The basics

Binary search finds a value in a sorted array by checking the middle element and throwing away the half that cannot contain the answer — again and again until it finds the value or runs out of range.

The problem it solves: a linear scan checks items one by one, so a million items means up to a million checks. Because the data is sorted, one comparison with the middle tells you which half the target is in, so each step halves the work: a million items need at most 20 checks.

The mental model: the guess-my-number game. "I'm thinking of a number from 1 to 100." Guess 50; "higher" — now it's 51–100. Guess 75; "lower". You never need more than 7 guesses.

Cost: O(log n) time. O(1) extra space for the loop version; O(log n) for the recursive one (its stack).

Explained

Linear search on a billion sorted records: up to a billion comparisons.

Binary search on the same records: 30.

The difference is not a faster computer. It's using the one fact you already paid for — the data is sorted — to throw away half of what's left with every look.

Guess my number

A friend thinks of a number between 1 and 100.

You say 50. "Higher." Every number from 1 to 50 is gone in one question. You say 75. "Lower." Now it's 51–74. You say 62. "Higher." 63–74…

You never need more than 7 guesses, because 100 → 50 → 25 → 13 → 7 → 4 → 2 → 1.

Now imagine your friend lies about the order — the numbers are written on cards in a random pile. "Higher" tells you nothing about which cards to discard. That's why binary search demands sorted input.

The invariant does the thinking

Hold one sentence true before every step:

If the target is in the array, it is somewhere in a[lo..hi].

• Start: lo = 0, hi = n - 1 — the whole array. True.
• mid = (lo + hi) // 2. If a[mid] == target, done.
• a[mid] < target → everything at or left of mid is too small → lo = mid + 1.
• a[mid] > target → everything at or right of mid is too big → hi = mid - 1.
• The range shrinks every step. When lo > hi it's empty → not present.

The +1 and -1 aren't magic: mid has been checked, so it leaves the range. Each step at least halves the range, so after k steps at most n / 2ᵏ remain → O(log n) steps.

Found in four looks

Ten items, target 40. Middle is 24 (too small) → right half. Middle is 52 (too big) → left part. Then 31, then 40. Four comparisons; a linear scan would take seven.

Not there — and where it would go

Target 20 isn't in the array. Watch the range shrink — 24, 8, 12, 19 — until lo passes hi. lo stops at index 4, between 19 and 24: exactly where 20 would be inserted. That's the insertion point bisect_left returns.

The library, and the template that generalises

import bisect

a = [3, 8, 12, 19, 24, 31, 40, 52, 67, 75]
bisect.bisect_left(a, 20)    # 4  → where 20 would go
bisect.bisect_left(a, 40)    # 6  → first index with a[i] >= 40

# Binary search on the answer: find the FIRST value where
# a yes/no question flips from False to True.
def first_true(lo, hi, ok):
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid          # mid might be the answer — keep it
        else:
            lo = mid + 1      # mid is definitely not
    return lo

# smallest k with k*k >= 50
first_true(0, 50, lambda k: k * k >= 50)   # 8  (7*7 = 49)

Same halving, but on a range of possible answers instead of an array: smallest box size that fits, earliest day a build broke, minimum speed to finish on time.

Why logarithms win

items (n)              linear (worst)   binary (worst)
────────────────────────────────────────────────────
100                    100              7
1,000                  1,000            10
1,000,000              1,000,000        20
1,000,000,000          10⁹              30
8 billion (every person) 8 × 10⁹         33

Doubling the data adds one comparison.

The catch is the sort. Sorting costs O(n log n) once. If you search once, just scan: O(n). If you search many times (k searches), sort once and binary search: O(n log n + k log n) beats O(k · n) quickly.

Binary search needs random access (jump to index mid in O(1)). On a linked list, finding the middle costs O(n), so the advantage disappears. Databases get the same effect on disk with B-tree indexes.

Gotchas

• Unsorted input — no error, just wrong answers. Sort first, or don't use it.
• lo < hi vs lo <= hi — the exact-match version needs <=, or it skips checking the last remaining element.
• lo = mid instead of mid + 1 — with lo = 0, hi = 1, mid stays 0 and the loop never ends.
• Overflow in Java/C/C++ — (lo + hi) / 2 can exceed the int range; write lo + (hi - lo) / 2. Python ints don't overflow.
• Duplicates — the basic version returns some matching index, not the first. Use bisect_left for the first, bisect_right - 1 for the last.
• Linked lists — no O(1) jump to the middle, so binary search is O(n) there.

Words to know

In two minutes

• Binary search needs a sorted array; each comparison with the middle discards half the remaining range.
• Time O(log n): 1,000 items → 10 checks, 1,000,000 → 20, 1,000,000,000 → 30. Space O(1) iterative, O(log n) recursive.
• Keep an invariant — 'if it's here, it's in a[lo..hi]' — and every +1/-1 follows from it.
• Loop while lo <= hi; move lo = mid + 1 or hi = mid - 1, because mid has already been checked.
• When the target is missing, lo ends at the insertion point — what bisect.bisect_left returns.
• The bigger idea: binary search works on any yes/no question that flips once (false…false, true…true) — 'binary search on the answer'.
• If you search only once, a linear scan beats sorting first: O(n) vs O(n log n).

Test yourself

There are 8 questions, 4 puzzles and 6 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.