AmouAI Hub/Courses/Data Structures & Algorithms/Chapter 13

Part 3 · Recursion and Sorting · Chapter 13

Binary Search and Searching the Answer

Twenty questions gets you to any number under a million. The technique is easy; getting the boundary conditions right is where careers are made and interviews lost.

Reading

CLRS Ch. 2.3

Focus

Halving, precisely

Cost

O(log n)

Also

bisect · predicates

By the end of this chapter you can

Write a binary search that terminates and is correct, by naming its invariant
Explain the overflow bug in (lo + hi) / 2 and why Python is immune
Use bisect_left and bisect_right and say precisely how they differ
Recognise a problem that binary-searches a predicate rather than an array
Apply binary search to a rotated array and to a monotone answer space

1Halving

One comparison eliminates half of everything still possible. Twenty of them get you through a million.

Twenty questions

I am thinking of a number between 1 and 1,000,000. You may only ask “is it higher than X?”

Ask about 500,000. Whatever the answer, half a million numbers are gone. Ask about the middle of what is left. Twenty questions is enough — because 2²⁰ is just over a million.

Guessing one number at a time would take, on average, half a million questions.

n	Linear search (worst)	Binary search (worst)
10	10	4
1,000	1,000	10
1,000,000	1,000,000	20
1,000,000,000	1,000,000,000	30
10¹⁸	unfinishable	60

Look at the last row. Sixty comparisons to search a set larger than the number of grains of sand on Earth. Logarithmic growth is not “a bit faster” — it is a different category.

The precondition is absolute

Binary search requires sorted data. Not “mostly sorted” — sorted.

On unsorted data it does not fail loudly; it returns a confident wrong answer, because the “go left / go right” decision is meaningless. That silence is what makes it dangerous. If your data is not sorted, sorting costs O(n log n) — worth it only if you will search many times.

2Writing one that is actually correct

A famous result: most published binary searches were wrong for two decades. The fix is to name the invariant and never violate it.

Jon Bentley reported that when he asked professional programmers to write binary search, about 90% produced buggy code — and a bug in the JDK's own implementation survived from 1997 to 2006. This is a five-line algorithm.

The reason is that there are four independent decisions and every combination compiles:

Is hi the last index, or one past it?
Is the loop while lo < hi or while lo <= hi?
Does lo become mid or mid + 1?
Does hi become mid or mid - 1?

Pick a consistent set and state the invariant they maintain. Here is the version this course uses:

binary_search.py

def binary_search(xs, target):
    """Return an index of target in the sorted list xs, or -1.

    INVARIANT: if target is present, it is somewhere in xs[lo..hi].
    Every branch must preserve that, and the loop must shrink the range.
    """
    lo, hi = 0, len(xs) - 1        # hi is INCLUSIVE
    while lo <= hi:                # so the range is empty when lo > hi
        mid = lo + (hi - lo) // 2
        if xs[mid] == target:
            return mid
        elif xs[mid] < target:
            lo = mid + 1           # mid is ruled out, so +1
        else:
            hi = mid - 1           # mid is ruled out, so -1
    return -1                      # lo passed hi: the range is empty

Two rules that prevent every binary-search bug

Say what the range means, and never break it. Here hi is inclusive, so the empty range is lo > hi, so the loop condition is <=. Those three facts must agree.
Every iteration must shrink the range. Because xs[mid] has been tested and ruled out, mid ± 1 is safe. Writing lo = mid with an inclusive hi is the classic infinite loop.

The overflow bug

overflow.py

# The version everyone writes:
mid = (lo + hi) // 2

# In a language with fixed-width integers, lo + hi can OVERFLOW when both
# are large — becoming negative, and indexing out of bounds. That is the
# bug that lived in the JDK for nine years.

# The fix, which costs nothing:
mid = lo + (hi - lo) // 2

# hi - lo is always small, so the sum never overflows.
#
# Python's integers are arbitrary precision, so you are immune here. Write
# it the safe way anyway: it is the same length, and one day you will be
# writing C or Java or Rust.

3bisect: the version you should call

Python ships a correct binary search. It answers a slightly different and usually more useful question.

The standard library's bisect module does not ask “is it here?” It asks “where would it go?” — which is strictly more informative, and answers the membership question as a special case.

bisect.py

from bisect import bisect_left, bisect_right, insort

xs = [10, 20, 20, 20, 30, 40]

bisect_left(xs, 20)    # 1  — index of the FIRST 20
bisect_right(xs, 20)   # 4  — index just past the LAST 20
bisect_right(xs, 20) - bisect_left(xs, 20)   # 3 — how many 20s there are

bisect_left(xs, 25)    # 4  — where 25 WOULD be inserted
bisect_left(xs, 5)     # 0  — before everything
bisect_left(xs, 99)    # 6  — after everything

# Membership, using bisect:
def contains(xs, target):
    i = bisect_left(xs, target)
    return i < len(xs) and xs[i] == target

# Keep a list sorted as you insert (O(n) for the shift, O(log n) to find):
insort(xs, 25)         # xs is now [10,20,20,20,25,30,40]

Question	Call
Is `x` present?	`i = bisect_left(xs, x); i < len(xs) and xs[i] == x`
How many copies of `x`?	`bisect_right(xs, x) - bisect_left(xs, x)`
First element ≥ x	`xs[bisect_left(xs, x)]`
First element > x	`xs[bisect_right(xs, x)]`
Last element < x	`xs[bisect_left(xs, x) - 1]`
Count of elements in `[a, b]`	`bisect_right(xs, b) - bisect_left(xs, a)`

Learn these six lines

Nearly every “find the nearest”, “count in a range” or “insert keeping sorted” problem is one of the rows above. Writing your own binary search for them is how you introduce an off-by-one at 2am.

Since Python 3.10, bisect also takes a key= argument, so you can search a list of objects by one field without building a parallel list.

4Binary searching a predicate

The real power of binary search is that it needs no array at all — only a yes/no question whose answer flips exactly once.

Forget arrays. Binary search works on any monotone predicate: a yes/no question over an ordered range that is False up to some point and True from there on.

predicate.py

#  is_ok(x):   F  F  F  F  T  T  T  T  T
#              ────────────┬────────────
#                          the boundary we want

def first_true(lo, hi, is_ok):
    """Smallest x in [lo, hi] with is_ok(x) True. Assumes monotone."""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if is_ok(mid):
            hi = mid          # mid MIGHT be the answer — keep it
        else:
            lo = mid + 1      # mid is definitely not — discard it
    return lo

# Note the asymmetry: hi = mid (inclusive, might be the answer)
# but lo = mid + 1 (exclusive, ruled out). That is what makes it
# find the FIRST true rather than any true.

Once you have that, a whole family of problems becomes mechanical. The pattern is always: guess an answer, ask whether it is feasible, and binary search on feasibility.

Problem	Search over	The predicate
Integer square root of n	0 … n	`x*x >= n`
Ship packages in D days: least capacity	max weight … total weight	“can we finish in D days at this capacity?”
Minimum eating speed to finish in H hours	1 … max pile	“does speed k finish in time?”
Split an array into k parts, minimise the largest part	max … sum	“can we split with no part exceeding X?”
First bad version in a release history	1 … n	`is_bad(v)`

ship_capacity.py

# Worked example: least ship capacity to deliver all packages in D days.
# The array is NOT sorted, and we are not searching it — we are searching
# the space of possible answers.

def least_capacity(weights, days):
    def days_needed(cap):
        d, load = 1, 0
        for w in weights:
            if load + w > cap:
                d += 1
                load = 0
            load += w
        return d

    lo = max(weights)        # must fit the heaviest single package
    hi = sum(weights)        # one day, everything at once
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if days_needed(mid) <= days:
            hi = mid         # feasible — try smaller
        else:
            lo = mid + 1     # infeasible — must go bigger
    return lo

# The predicate is monotone: if capacity C works, C+1 certainly works.
# THAT is the only property binary search needs.

How to spot one

Three signals, and any of them should make you think “binary search the answer”:

The wording is “minimise the maximum” or “maximise the minimum”.
Checking a candidate answer is easy, but finding it looks hard.
If a candidate works, every larger (or smaller) one also works.

That last one is the monotonicity requirement, and it is the only thing you must verify before applying the technique.

5Variants worth knowing

Three modifications that show up constantly, each a small change to the same skeleton.

Rotated sorted array

A sorted array rotated at an unknown point: [4,5,6,7,0,1,2]. It is not sorted, so plain binary search fails — but at every step at least one half is still sorted, and you can tell which by comparing the endpoints.

rotated.py

def search_rotated(xs, target):
    lo, hi = 0, len(xs) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if xs[mid] == target:
            return mid
        if xs[lo] <= xs[mid]:            # the LEFT half is sorted
            if xs[lo] <= target < xs[mid]:
                hi = mid - 1             # target is in that sorted half
            else:
                lo = mid + 1
        else:                            # then the RIGHT half is sorted
            if xs[mid] < target <= xs[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Search a 2-D matrix

If each row is sorted and each row starts after the previous ends, treat the whole matrix as one flat sorted array and convert the index with divmod.

matrix.py

def search_matrix(grid, target):
    rows, cols = len(grid), len(grid[0])
    lo, hi = 0, rows * cols - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        r, c = divmod(mid, cols)       # flat index → (row, col)
        if grid[r][c] == target:
            return (r, c)
        elif grid[r][c] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return None

Binary search on a real-valued answer

When the answer is a float there is no “next value”, so you cannot loop until lo == hi. Loop a fixed number of times instead — a hundred iterations halves the range by 2¹⁰⁰, which is far past double precision.

float_search.py

def sqrt(n, iterations=100):
    lo, hi = 0.0, max(1.0, n)
    for _ in range(iterations):
        mid = (lo + hi) / 2
        if mid * mid < n:
            lo = mid
        else:
            hi = mid
    return lo

# Fixed iteration count instead of a tolerance: no risk of an infinite
# loop from floating-point comparison, and the cost is a known constant.

Binary search

O(log n)

Predicate search

O(log(range) × check)

Rotated array

O(log n)

Sort then search once

O(n log n)

Space

O(1) iterative

The three bugs to test for, every time

Infinite loop. A branch that does not shrink the range. Test on a two-element list.
Off by one. Test the first element, the last element, and a target smaller and larger than everything.
Duplicates. Plain binary search returns an index, not the first. If you need first or last, use bisect_left / bisect_right.

What to carry forward

Each comparison discards half of what is still possible. Sixty comparisons search a quintillion items.
Name the invariant — what the range means — and make the loop condition, the update rules and the empty case all agree with it.
Every branch must shrink the range. lo = mid with an inclusive hi is the classic infinite loop.
Write mid = lo + (hi - lo) // 2. Python cannot overflow, but the habit transfers to languages that can.
bisect_left finds the first position, bisect_right the position past the last. Six one-liners cover most range questions.
Binary search needs no array — only a monotone predicate. 'Minimise the maximum' almost always means binary-search the answer.

>_Playground

A correct binary search, the bisect family, and a predicate search on an unsorted array. Try breaking the boundaries.

scratch.pypython not loaded

from bisect import bisect_left, bisect_right

def binary_search(xs, target):
    lo, hi = 0, len(xs) - 1
    steps = 0
    while lo <= hi:
        steps += 1
        mid = lo + (hi - lo) // 2
        if xs[mid] == target:
            return mid, steps
        elif xs[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, steps

data = list(range(0, 2_000_000, 2))          # a million even numbers
for t in [0, 1_000_000, 1_999_998, 999_999]:
    i, s = binary_search(data, t)
    print(f"search {t:>9}: index={i:>8}  steps={s}")
print(f"(linear search would take up to {len(data):,} steps)")
print()

# ---- bisect, and why there are two of them ----
xs = [10, 20, 20, 20, 30, 40]
print("xs =", xs)
print("bisect_left (xs, 20) =", bisect_left(xs, 20), " <- first 20")
print("bisect_right(xs, 20) =", bisect_right(xs, 20), " <- just past the last 20")
print("count of 20s          =", bisect_right(xs, 20) - bisect_left(xs, 20))
print("where would 25 go?    =", bisect_left(xs, 25))
print("first element >= 25   =", xs[bisect_left(xs, 25)])
print()

# ---- searching the ANSWER, on unsorted data ----
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
days = 5

def days_needed(cap):
    d, load = 1, 0
    for w in weights:
        if load + w > cap:
            d += 1
            load = 0
        load += w
    return d

lo, hi = max(weights), sum(weights)
print(f"searching capacities {lo}..{hi} for the least that finishes in {days} days")
while lo < hi:
    mid = lo + (hi - lo) // 2
    ok = days_needed(mid) <= days
    print(f"  try capacity {mid:3} -> {days_needed(mid)} days  {'OK' if ok else 'too slow'}")
    if ok:
        hi = mid
    else:
        lo = mid + 1
print("answer:", lo)
print()
print("Note the weights list is NOT sorted, and we never searched it.")
print("We searched the space of possible ANSWERS.")

Real Python, running in your browser. Nothing is installed or uploaded.

Output appears here. The first run takes a few seconds while Python loads.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.

All Warm-up Core Challenge Reset chapter

Chapter 14 — Trees and Binary Trees

A family tree, a filesystem, a table of contents, the DOM. Once you see the shape you see it everywhere — and four traversals visit any of them.

Continue →