Binary search, from first idea to production

Think of a number between 1 and 100. I can find it in at most seven guesses, as long as you tell me “higher” or “lower” each time. Not because I’m lucky: every guess throws away half of what’s left, and you can only halve 100 seven times before one number remains. That’s binary search, and the same seven-step trick finds one row among ten million in a database, one bad commit among a thousand in git, and the smallest server that can survive a traffic spike.

It’s also the algorithm people get wrong most often while being sure they got it right. The idea fits in a sentence; the code has four places to put a + 1 or a - 1, and each wrong choice gives a loop that works on most inputs and fails on some. The fix isn’t memorizing a template. It’s knowing what your two boundaries mean.

By the end of this article you’ll be able to write binary search without off-by-one errors, use Python’s bisect module properly, spot the problems where you search over answers instead of an array, explain the overflow bug that sat in Java for nine years, measure why a plain sorted array is slow on big data, and see how B-tree indexes and git bisect are the same idea at larger scale. The last section covers where sorted lookups carry real decisions in ezychat.io, most of them in PostgreSQL indexes. Start at Beginner if you’ve never written the loop. If you have, and still sometimes get it wrong, start at Intermediate.

Beginner: halve what’s left

The guessing game

Here’s the game as a program. It always guesses the middle of the numbers that are still possible:

def play(secret, low=1, high=100):
    guesses = []
    while True:
        guess = (low + high) // 2           # always guess the middle of what's left
        guesses.append(guess)
        if guess == secret:
            return guesses
        if guess < secret:
            low = guess + 1                 # "higher": the guess and everything below it are out
        else:
            high = guess - 1                # "lower": the guess and everything above it are out

print(play(64))
print(max(len(play(s)) for s in range(1, 101)))
print(sum(len(play(s)) for s in range(1, 101)) / 100)
# [50, 75, 62, 68, 65, 63, 64]
# 7
# 5.8

// is integer division: (1 + 100) // 2 is 50, not 50.5. The second line tries every secret from 1 to 100 and reports the most guesses any of them needed: seven. On average it’s 5.8.

Notice what makes the game work. The answer “higher” tells you something about every number below the guess, not only the guess itself. If 50 is too low, so are 1 to 49, and you never have to ask about them. One question, fifty numbers gone.

Why the list has to be sorted

Now the same game with a list of numbers instead of a range. You have a price list and want to know where 46 is. The obvious way is to look at each item in turn. That’s linear search:

def linear_search(items, target):
    for i, item in enumerate(items):
        if item == target:
            return i
    return -1

prices = [3, 8, 12, 15, 21, 27, 34, 40, 46, 55, 61, 70]
print(linear_search(prices, 46), linear_search(prices, 47))
# 8 -1

It returns the index (the position, counting from 0) of the match, or -1 if there’s none. It works on any list, in any order. The cost is the problem: to say “47 isn’t here”, it has to look at all twelve items, because any one of them could have been 47.

Binary search can say “47 isn’t here” after looking at four, but only because this list is sorted: each item is at least as big as the one before it. Sorted order is what lets one comparison speak for a whole half. If the middle item is 34 and you want 46, everything left of 34 is smaller than 34, so it’s smaller than 46 too. On an unsorted list that conclusion is false, and binary search gives wrong answers without any error:

unsorted = [40, 3, 70, 15, 8, 55, 21]
print(binary_search(unsorted, 70), binary_search(unsorted, 8))
# -1 -1

Both 70 and 8 are in that list. Binary search (the function is in the next section) looked at 15 in the middle, decided 70 must be to the right, and never looked left, where 70 actually is. This is the first rule, and it’s not negotiable: binary search only works on data sorted by the same rule you compare with.

Binary search in code

Two variables mark the part of the list that’s still in play. lo is the index of its first item and hi the index of its last. The loop looks at the item halfway between them, mid, and moves one of the boundaries past it:

def binary_search(items, target):
    lo, hi = 0, len(items) - 1          # the part still in play: items[lo] .. items[hi]
    while lo <= hi:                     # stop when nothing is left
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1                # target can only be to the right of mid
        else:
            hi = mid - 1                # target can only be to the left of mid
    return -1

prices = [3, 8, 12, 15, 21, 27, 34, 40, 46, 55, 61, 70]
print(binary_search(prices, 46), binary_search(prices, 47))
print(binary_search(prices, 3), binary_search(prices, 70), binary_search([], 5))
# 8 -1
# 0 11 -1

Read each line against the comment beside it. lo = mid + 1 and hi = mid - 1 both skip mid itself, because we’ve just checked it and it isn’t the target. The loop runs while lo <= hi, meaning “at least one item is still in play”; when lo passes hi, the range is empty and the answer is -1. The last three calls are the edges worth testing on any search you write: the first item, the last item, and an empty list.

Step through it. Grey cells are ruled out; the counter compares binary search with a left-to-right scan:

Try a missing value and watch lo and hi cross. Then switch the size to 64: binary search needs one more comparison each time the array doubles, while the linear count doubles.

How many steps? Halving, written out

Each comparison at least halves what’s left. Start with n items: after one step about n/2 remain, after two n/4, after k steps n/2ᵏ. The search ends when one item is left, so the number of steps is how many times you can halve n before you reach 1. That number has a name, the base-2 logarithm of n, written log₂ n. It’s the answer to “2 to the power of what is n?”: log₂ 8 is 3 because 2 × 2 × 2 is 8.

You don’t need the formula to feel it. Count it on sorted lists far too big to build: a Python range can be indexed like a list without storing anything, so this searches a billion numbers in memory that holds four:

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

for n in (100, 1_000, 1_000_000, 1_000_000_000):
    evens = range(0, 2 * n, 2)          # n sorted numbers; a range never builds the list
    worst = max(count_steps(evens, t) for t in (-1, 1, 2 * n, evens[-1], evens[n // 3]))
    print(f"{n:>13,} items: {worst} steps at most")
#           100 items: 7 steps at most
#         1,000 items: 10 steps at most
#     1,000,000 items: 20 steps at most
# 1,000,000,000 items: 30 steps at most

A thousand times more data costs ten more steps. That’s what O(log n) means, read “order log n”: the work grows with the logarithm of the size, so doubling the data adds one step. Linear search is O(n): doubling the data doubles the work. At a billion items, that’s 30 comparisons against up to a billion.

Here it is with a clock. Looking up 1,000 IDs in a sorted list of a million, with linear search done by Python’s own C code (list.index) against binary search in plain Python, on my laptop (an M1 Pro, Python 3.13):

import random, time

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
        else:
            hi = mid - 1
    return -1

random.seed(5)
ids = sorted(random.sample(range(10_000_000), 1_000_000))   # a million sorted IDs
queries = [random.choice(ids) for _ in range(1_000)]

start = time.perf_counter()
a = [ids.index(q) for q in queries]                 # linear search, done by C code
linear = time.perf_counter() - start

start = time.perf_counter()
b = [binary_search(ids, q) for q in queries]        # binary search, in plain Python
binary = time.perf_counter() - start

print(a == b)
print(f"linear: {linear:.2f} s   binary: {binary * 1000:.2f} ms   ratio: {linear / binary:,.0f}x")
# True
# linear: 16.69 s   binary: 3.67 ms   ratio: 4,549x

A second run gave 20.59 seconds against 3.92 milliseconds. The ratio moves around; the shape doesn’t. The slow language with the better algorithm wins by three orders of magnitude, because 20 steps beat half a million no matter how fast each step is.

When to reach for it, and when not

Binary search pays when the data is sorted once and searched many times: a price table, a list of time ranges, an index, a release history. It’s a poor deal when you’d have to sort just to search once. Sorting n items costs about n × log₂ n comparisons, which is more than the n a single linear scan needs.

The other competitor is a hash map. For “is this exact key present?”, a dict or set answers in about one step and beats binary search outright. Binary search wins whenever the question involves order: the nearest value, the first item at least this big, everything between two dates, the position a new item should go. A hash map scatters keys on purpose and can’t answer any of those.

def find_name(names, target):
    lo, hi = 0, len(names) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if names[mid] == target:
            return mid
        if names[mid] < target:         # strings compare alphabetically, character by character
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

staff = ["Aisha", "Ben", "Chen", "Dana", "Eli", "Farah", "Gopal", "Hana"]
print(find_name(staff, "Farah"), find_name(staff, "Aisha"), find_name(staff, "Zoe"))
fruit = ["apple", "Banana", "cherry"]           # looks sorted to a person
print(find_name(fruit, "apple"), sorted(fruit))
# 5 0 -1
# -1 ['Banana', 'apple', 'cherry']

def guesses_needed(n):
    steps = 0
    while n > 0:
        n //= 2                         # one guess: what's left is at most half, rounded down
        steps += 1
    return steps

def worst_by_playing(n):
    worst = 0
    for secret in range(1, n + 1):
        lo, hi, count = 1, n, 0
        while True:
            count += 1
            g = (lo + hi) // 2
            if g == secret:
                break
            lo, hi = (g + 1, hi) if g < secret else (lo, g - 1)
        worst = max(worst, count)
    return worst

print([guesses_needed(n) for n in (1, 2, 3, 7, 8, 100, 1000)])
print(all(guesses_needed(n) == worst_by_playing(n) for n in range(1, 2000)))
print(guesses_needed(8_000_000_000), (8_000_000_000).bit_length())
# [1, 2, 2, 3, 4, 7, 10]
# True
# 33 33

Intermediate: invariants, bounds and searching for answers

The Beginner loop finds a match. Real problems ask for more: the first match, the last one, where a missing value would go, the smallest setting that works. Each needs a slightly different loop, and this is where the bugs live. The way through is to stop thinking about templates and start thinking about promises.

What lo and hi promise

A loop invariant is a statement that’s true before the loop starts and stays true after every pass. For the Beginner search it is:

If the target is in the list, it’s somewhere in items[lo..hi].

At the start, lo = 0 and hi = len - 1 cover everything, so it’s true. Each branch keeps it true: lo = mid + 1 only discards items that are smaller than the target, and hi = mid - 1 only discards bigger ones. When the loop ends with lo > hi, the range is empty, and the invariant says the target can’t be anywhere. The code is correct because the invariant holds, not because the tests pass.

Every binary search you write should answer four questions, out loud or in a comment:

1. What do lo and hi mean? Is hi the last candidate (a closed range, both ends included) or one past it (a half-open range, lo included, hi not)?
2. When is the range empty? Closed: when lo > hi, so loop while lo <= hi. Half-open: when lo == hi, so loop while lo < hi.
3. What does each branch discard? It must discard mid if mid is definitely not the answer, and keep it if it might be.
4. Does every pass make the range smaller? If one branch can leave lo and hi unchanged, the loop never ends.

The off-by-one family

Most broken binary searches mix the answers from two different conventions. Here are the legal combinations:

In the half-open convention hi = mid both discards and keeps nothing extra: hi is already “one past the last candidate”, so setting it to mid removes mid and everything after. That’s why lower bound, which wants to keep mid as a possible answer, is written half-open. More on that in a moment.

The bug that bites hardest is the infinite loop. Say you want the last position whose value is at most x. A candidate mid that’s small enough might be the answer, so you keep it with lo = mid:

def last_at_most_broken(a, x, max_loops=20):
    """Last index i with a[i] <= x. Looks right; isn't."""
    lo, hi, loops = 0, len(a) - 1, 0
    while lo < hi:
        loops += 1
        if loops > max_loops:
            return f"stuck: lo={lo} hi={hi} mid={(lo + hi) // 2} forever"
        mid = (lo + hi) // 2            # rounds down, so mid can equal lo
        if a[mid] <= x:
            lo = mid                    # ...and then lo never moves
        else:
            hi = mid - 1
    return lo

def last_at_most(a, x):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi + 1) // 2        # round up, so mid is never lo
        if a[mid] <= x:
            lo = mid
        else:
            hi = mid - 1
    return lo

a = [1, 3, 5, 7]
print(last_at_most_broken(a, 6))
print(last_at_most(a, 6), last_at_most(a, 7), last_at_most(a, 1))
# stuck: lo=2 hi=3 mid=2 forever
# 2 3 0

With two items left, lo = 2 and hi = 3, (2 + 3) // 2 is 2, a[2] = 5 is at most 6, and lo = mid sets lo to 2 again. Question 4 fails. The rule is short: if a branch sets lo = mid, round mid up. (last_at_most also assumes a[0] <= x; the cleaner way to get the same answer, without that assumption, is the upper bound below minus one.)

Lower bound and upper bound

These two questions come up more than “find any match”:

• Lower bound of x: the first position whose value is at least x (≥ x).
• Upper bound of x: the first position whose value is greater than x (> x).

Both always have an answer. If nothing qualifies, the answer is len(a), which means “after the end”, and it’s exactly where you’d insert x to keep the list sorted. That’s why the range is half-open: the answer can be len(a), so hi starts there.

def lower_bound(a, x):
    """First index i with a[i] >= x, or len(a) if there is none."""
    lo, hi = 0, len(a)              # the answer is an index from lo to hi; hi = len(a) means "after everything"
    while lo < hi:                  # stop when one position is left
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1            # mid is too small, so the answer is after it
        else:
            hi = mid                # mid might be the answer: keep it
    return lo

def upper_bound(a, x):
    """First index i with a[i] > x, or len(a) if there is none."""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= x:             # the only change: <= instead of <
            lo = mid + 1
        else:
            hi = mid
    return lo

a = [1, 2, 4, 4, 4, 7, 9]
print(lower_bound(a, 4), upper_bound(a, 4))     # the 4s live in a[2:5]
print(lower_bound(a, 5), upper_bound(a, 5))     # no 5: both point where it would go
print(lower_bound(a, 0), lower_bound(a, 10))    # before everything, after everything
print(upper_bound(a, 4) - lower_bound(a, 4), "copies of 4")

import bisect, random
random.seed(3)
for _ in range(10_000):
    arr = sorted(random.choices(range(20), k=random.randint(0, 15)))
    x = random.randint(-2, 22)
    assert lower_bound(arr, x) == bisect.bisect_left(arr, x)
    assert upper_bound(arr, x) == bisect.bisect_right(arr, x)
print("10,000 random checks agree with bisect")
# 2 5
# 5 5
# 0 7
# 3 copies of 4
# 10,000 random checks agree with bisect

The pair is more useful than either alone. a[lower:upper] is every copy of x, upper - lower counts them, and if the two are equal, x isn’t there and both point at its insertion spot. Go back to the demo above and switch to the bound modes: the array now has duplicates and an extra “end” slot, because “after the end” is a legal answer.

Python’s bisect module

You rarely need to write those two functions in Python, because the standard library has them in C. bisect_left is lower bound and bisect_right (also called plain bisect) is upper bound:

from bisect import bisect_left, bisect_right, bisect, insort

a = [1, 2, 4, 4, 4, 7, 9]
print(bisect_left(a, 4), bisect_right(a, 4), bisect(a, 4))   # bisect is bisect_right
print(bisect_left(a, 4, lo=3))                                # search only a[3:]

insort(a, 5)                    # find the spot with bisect_right, then list.insert
print(a)

# Mapping a number to a band: the classic use of bisect_right.
def grade(score, breakpoints=(60, 70, 80, 90), grades="FDCBA"):
    return grades[bisect_right(breakpoints, score)]

print([grade(s) for s in (33, 60, 77, 89, 90, 100)])
# 2 5 5
# 3
# [1, 2, 4, 4, 4, 5, 7, 9]
# ['F', 'D', 'C', 'B', 'A', 'A']

The grade function is the pattern I’d remember from this whole module. A sorted list of breakpoints plus bisect_right turns “which band does this number fall in?” into one line, and the choice of bisect_right decides the boundary: a score of exactly 60 is a D, not an F. Use bisect_left and 60 would be an F. Pick the one that matches the rule you’ve been given, and test the boundary values themselves.

Since Python 3.10 every function takes key=, so you can search a list of records sorted by one field without building a separate list of keys. There’s a trap in it:

from bisect import bisect_left, bisect_right, insort
from datetime import datetime
from operator import itemgetter

# Log events sorted by time. Find everything between 10:00 and 10:30.
events = [
    (datetime(2026, 11, 3, 9, 58), "deploy started"),
    (datetime(2026, 11, 3, 10, 2), "health check failed"),
    (datetime(2026, 11, 3, 10, 2), "rollback started"),
    (datetime(2026, 11, 3, 10, 21), "rollback done"),
    (datetime(2026, 11, 3, 10, 40), "deploy started"),
]
when = itemgetter(0)

start = bisect_left(events, datetime(2026, 11, 3, 10, 0), key=when)    # x is already a key
end = bisect_right(events, datetime(2026, 11, 3, 10, 30), key=when)
print([msg for _, msg in events[start:end]])

# insort applies key to the new item itself, so pass the whole record:
insort(events, (datetime(2026, 11, 3, 10, 5), "alert fired"), key=when)
print([msg for _, msg in events][:4])

# The trap: bisect does NOT apply key to x.
try:
    bisect_left(events, (datetime(2026, 11, 3, 10, 0), ""), key=when)
except TypeError as e:
    print("TypeError:", e)
# ['health check failed', 'rollback started', 'rollback done']
# ['deploy started', 'health check failed', 'rollback started', 'alert fired']
# TypeError: '<' not supported between instances of 'datetime.datetime' and 'tuple'

(The log lines are made up for the example.) bisect_left(a, x, key=f) compares x with f(a[i]), so x must already be a key. insort(a, x, key=f) compares f(x) with f(a[i]), because it needs the whole record to insert. CPython’s source does exactly that: insort calls the key on x first, bisect doesn’t. The range query is the other pattern worth keeping: bisect_left on the start and bisect_right on the end gives a half-open slice of everything inside, duplicates included.

What it costs

Binary search is O(log n) comparisons and O(1) extra memory: three integers, whatever the size. Two costs hide around it.

The first is getting the data sorted, O(n log n) once. That’s cheap if you search a lot, and wasted if you search once.

The second is keeping it sorted. insort finds the spot in O(log n), then list.insert shifts every later item one place to the right, which is O(n). Insert n items one by one and you’ve built an O(n²) loop with a logarithm in its name:

import random, time
from bisect import insort

random.seed(11)
for n in (100_000, 400_000):
    data = [random.random() for _ in range(n)]

    start = time.perf_counter()
    kept = []
    for x in data:
        insort(kept, x)             # O(log n) to find the spot, O(n) to shift the tail
    one_by_one = time.perf_counter() - start

    start = time.perf_counter()
    batch = sorted(data)            # sort once at the end
    at_once = time.perf_counter() - start

    print(f"n={n:>7,}: insort {one_by_one:.2f} s, sorted() {at_once * 1000:.0f} ms, same {kept == batch}")
# n=100,000: insort 1.31 s, sorted() 11 ms, same True
# n=400,000: insort 20.21 s, sorted() 58 ms, same True

Four times the data, fifteen times the insort time, on my laptop. If you need the sorted order only at the end, sort at the end. If you need it after every insert, and the data is large, you want a structure built for that: a balanced tree, a skip list (what Redis sorted sets use), or the third-party sortedcontainers package. For a few thousand items, insort is fine, and I’d use it without a second thought.

Search the answer, not the array

Here’s a problem that doesn’t look like searching at all. A ship carries packages from a conveyor belt, in order. Each day it loads packages until the next one would exceed its capacity, then sails. What’s the smallest capacity that ships everything within D days?

def days_needed(weights, capacity):
    """Load packages in order; start a new day when the next one won't fit."""
    days, load = 1, 0
    for w in weights:
        if load + w > capacity:
            days += 1
            load = 0
        load += w
    return days

def ship_within_days(weights, days):
    lo, hi = max(weights), sum(weights)     # smallest and largest capacities worth trying
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(weights, mid) <= days:
            hi = mid                        # mid works: the answer is mid or smaller
        else:
            lo = mid + 1                    # mid fails: the answer is bigger
    return lo

weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print([days_needed(weights, c) <= 5 for c in range(10, 20)])
print(ship_within_days(weights, 5))
print(ship_within_days([3, 2, 2, 4, 1, 4], 3), ship_within_days([1, 2, 3, 1, 1], 4))
# [False, False, False, False, False, True, True, True, True, True]
# 15
# 6 3

There’s no array being searched. What’s sorted is the answers. Ask “does capacity c work?” for every c from 10 upwards and you get False, False, …, False, True, True, …, True. It can’t flip back: if a ship of capacity 15 manages in five days, a bigger ship certainly can. A yes/no question with that shape is called a monotonic predicate, and the boundary where it flips from False to True is a lower bound over the answers. So binary search finds it, checking about log₂(55 − 10) ≈ 6 capacities instead of all 46.

The bounds of the search come from the problem, and they’re worth getting right. Below the heaviest package nothing works, because that package never fits; at the total weight everything ships in one day. Each check costs one pass over the packages, so the whole search is O(n × log(sum − max)).

Turn off “Show every capacity’s answer” to see what the search actually knows: only the handful of capacities it checked. Then try 7, 2, 5, 10, 8 with 2 days.

The general shape is worth writing once and reusing:

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi] with ok(x) True, assuming ok goes False...False True...True.
    Returns hi + 1 if ok is never True."""
    hi += 1                             # room for the answer "never"
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

How to recognize these problems: the question asks for the minimum value that makes something possible, or the maximum value that keeps something safe, and you can check any single guess quickly even though you can’t compute the answer directly. Minimum speed to finish on time, maximum load before a server breaks its latency target, smallest batch size that fits in memory. If checking is easy and “bigger is always at least as good” (or always at least as bad), binary search the answer.

Rotated sorted arrays

A classic variation: a sorted array was rotated at an unknown point, like [4, 5, 6, 7, 0, 1, 2]. It isn’t sorted any more, but it’s two sorted runs, and binary search still works because of one fact: cut it anywhere, and at least one side of the cut is sorted.

To find the minimum, compare a[mid] with a[hi]. If a[mid] > a[hi], the drop lies between them, so the minimum is right of mid. Otherwise mid..hi climbs steadily and the minimum is mid or to its left:

def find_min_rotated(a):
    """Index of the smallest value in a sorted array rotated by an unknown amount (no duplicates)."""
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1                # the drop is to the right of mid
        else:
            hi = mid                    # mid..hi is sorted, so the minimum is mid or left of it
    return lo

print(find_min_rotated([4, 5, 6, 7, 0, 1, 2]), find_min_rotated([1, 2, 3]), find_min_rotated([2, 1]))
# 4 0 1

The predicate here is “is a[i] at most the last element?”, which is False across the first run and True across the second. It’s the same first-true search wearing a different coat. The no-duplicates condition matters: with duplicates, [1, 1, 1, 0, 1] can make a[mid] == a[hi] while the drop is on either side, and the worst case falls back to O(n).

def min_eating_speed(piles, h):
    def hours(k):
        return sum((p + k - 1) // k for p in piles)    # ceil(p / k) without floats
    return first_true(1, max(piles), lambda k: hours(k) <= h)

print(min_eating_speed([3, 6, 7, 11], 8))
print(min_eating_speed([30, 11, 23, 4, 20], 5), min_eating_speed([30, 11, 23, 4, 20], 6))
print(min_eating_speed([312884470], 312884469))
# 4
# 30 23
# 2

def smallest_divisor(nums, threshold):
    def total(d):
        return sum((n + d - 1) // d for n in nums)
    return first_true(1, max(nums), lambda d: total(d) <= threshold)

print(smallest_divisor([1, 2, 5, 9], 6), smallest_divisor([44, 22, 33, 11, 1], 5))
# 5 44

from bisect import bisect_left, bisect_right

def first_and_last(a, x):
    first = bisect_left(a, x)
    if first == len(a) or a[first] != x:
        return [-1, -1]                 # lower bound landed on something else: x is absent
    return [first, bisect_right(a, x) - 1]

print(first_and_last([5, 7, 7, 8, 8, 10], 8))
print(first_and_last([5, 7, 7, 8, 8, 10], 6))
print(first_and_last([], 0), first_and_last([2, 2], 2))

def count_between(a, low, high):
    """How many values v in sorted a have low <= v <= high."""
    return bisect_right(a, high) - bisect_left(a, low)

ages = [18, 21, 21, 25, 30, 30, 30, 41, 52, 67]
print(count_between(ages, 21, 30), count_between(ages, 31, 40), count_between(ages, 0, 100))
# [3, 4]
# [-1, -1]
# [-1, -1] [0, 1]
# 6 0 10

def search_rotated(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[lo] <= a[mid]:             # left half a[lo..mid] is sorted
            if a[lo] <= target < a[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                           # right half a[mid..hi] is sorted
            if a[mid] < target <= a[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

a = [4, 5, 6, 7, 0, 1, 2]
print([search_rotated(a, t) for t in (0, 4, 7, 2, 3)], search_rotated([1], 0))

import random
random.seed(8)
for _ in range(5_000):
    base = sorted(random.sample(range(100), random.randint(1, 12)))
    k = random.randrange(len(base))
    r = base[k:] + base[:k]
    assert r[find_min_rotated(r)] == min(r)
    t = random.randint(-1, 100)
    i = search_rotated(r, t)
    assert (i == -1 and t not in r) or r[i] == t
print("5,000 random rotations checked")
# [4, 0, 3, 6, -1] -1
# 5,000 random rotations checked

Advanced: overflow, floats, caches and galloping

The Intermediate loops are correct. This section is about what happens when they meet real machines: fixed-size integers, floating-point numbers, memory that’s much slower than the processor, and data that’s nearly in order already.

The bug that sat in the JDK for nine years

On June 2, 2006, Joshua Bloch published a short post on Google’s research blog titled “Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken”. The broken line was in the binary search he’d written for Java’s java.util.Arrays:

int mid = (low + high) / 2;

In Java an int holds at most 2³¹ − 1, about 2.1 billion. With an array of more than about a billion elements (2³⁰), low + high can pass that limit, wrap around to a negative number, and produce a negative mid, which throws an exception or reads the wrong place. Bloch wrote that the bug had been in the JDK for about nine years before someone’s program hit it, and that it was in Jon Bentley’s binary search in Programming Pearls too, the book that famously reported that only about ten percent of professional programmers, given ample time, wrote a correct binary search. Bentley also quoted Knuth: the first binary search was published in 1946, and the first one without bugs didn’t appear until 1962.

Python’s integers can’t overflow, so I’ll fake a 32-bit int with ctypes to watch it happen:

import ctypes

def int32(n):
    return ctypes.c_int32(n).value      # what a 32-bit signed int actually holds

low, high = 1_100_000_000, 1_200_000_000   # valid indexes into a 1.2-billion-element array
print("true midpoint        ", (low + high) // 2)
print("int32 (low + high)/2 ", int32(low + high) // 2)
print("low + (high - low)/2 ", low + (high - low) // 2)
print("(low + high) >>> 1   ", (int32(low + high) & 0xFFFF_FFFF) >> 1)  # unsigned shift
print("Python, any size     ", (10**30 + (10**30 + 2)) // 2)
# true midpoint         1150000000
# int32 (low + high)/2  -997483648
# low + (high - low)/2  1150000000
# (low + high) >>> 1    1150000000
# Python, any size      1000000000000000000000000000001

Bloch’s two fixes are in the middle lines. low + (high - low) / 2 never forms a sum bigger than high. (low + high) >>> 1 lets the sum wrap, then reinterprets its bits as unsigned with Java’s unsigned shift, which gives back the right answer because the true sum still fits in 32 unsigned bits. In C and C++ he recommended casting to unsigned int before adding.

Pure Python doesn’t have the bug: lo + hi is an arbitrary-precision integer that just grows. But CPython’s bisect is written in C, and its source has the fix with a comment pointing at the bug report:

mid = ((size_t)lo + hi) / 2;
/* The (size_t)cast ensures that the addition and subsequent division
   are performed as unsigned operations, avoiding difficulties from
   signed overflow.  (See issue 13496.) */

Go’s sort.Search does the same thing in its own idiom: h := int(uint(i+j) >> 1) // avoid overflow when computing h. My habit in any language with fixed-width integers is to write lo + (hi - lo) / 2 without thinking about whether the array can get that big. It costs nothing and removes the question.

Binary search on real numbers

Binary search also works on continuous ranges, where it’s called the bisection method: to solve f(x) = 0 when f is negative at one end and positive at the other, check the middle and keep the half where the sign changes. Square roots are the friendly example. The question is when to stop, since there’s no “one item left”:

import math

def sqrt_fixed(x, iterations=100):
    lo, hi = 0.0, max(1.0, x)
    for _ in range(iterations):         # each pass halves the interval, no matter its size
        mid = (lo + hi) / 2
        if mid * mid < x:
            lo = mid
        else:
            hi = mid
    return hi

def sqrt_eps(x, eps=1e-9, max_loops=10_000):
    lo, hi, loops = 0.0, max(1.0, x), 0
    while hi - lo > eps:                # "stop when the interval is small enough"
        loops += 1
        if loops > max_loops:
            return f"stuck after {max_loops:,} loops: hi - lo = {hi - lo}"
        mid = (lo + hi) / 2
        if mid * mid < x:
            lo = mid
        else:
            hi = mid
    return hi

def sqrt_until_stuck(x):
    lo, hi, loops = 0.0, max(1.0, x), 0
    while True:
        mid = (lo + hi) / 2
        if mid == lo or mid == hi:      # no float left between lo and hi
            return hi, loops
        loops += 1
        if mid * mid < x:
            lo = mid
        else:
            hi = mid

print(sqrt_fixed(2), math.sqrt(2))
print(sqrt_eps(2))
print(sqrt_eps(1e12))                   # floats near 10**6 are about 1.2e-10 apart: fine
print(sqrt_eps(1e20))                   # floats near 10**10 are about 1.9e-6 apart
print(math.ulp(1e10))
print(sqrt_until_stuck(1e20), sqrt_until_stuck(2))
# 1.4142135623730951 1.4142135623730951
# 1.4142135623842478
# 1000000.0000000006
# stuck after 10,000 loops: hi - lo = 1.9073486328125e-06
# 1.9073486328125e-06
# (10000000000.0, 85) (1.4142135623730951, 53)

The epsilon version has a bug that never shows on small inputs. A float has about 16 significant digits, so the gap between neighboring floats grows with the number: near 10¹⁰ it’s about 1.9 × 10⁻⁶ (math.ulp reports the gap). Asking for an interval narrower than 10⁻⁹ there asks for something that doesn’t exist, and the loop runs forever, which is why mine has a loop cap.

So I use one of two stopping rules. A fixed iteration count is simple and always terminates: 100 halvings shrink any interval by 2¹⁰⁰, far past what a 64-bit float can represent, so the answer is as precise as floats allow. Or stop when the midpoint equals an endpoint, which means no float is left between them; it ended here in 85 and 53 passes. Use a relative tolerance, hi - lo > eps * max(1, abs(lo)), if you genuinely need to stop early. Never an absolute epsilon on numbers of unknown size.

Why binary search gets slow on big arrays

Everything so far counted comparisons. On a modern CPU, comparisons are almost free. What costs time is fetching memory: a value already in the processor’s cache arrives in a few nanoseconds, while one that has to come from main memory takes closer to a hundred. Memory moves in cache lines of 64 bytes, sixteen 4-byte integers at a time.

Binary search is about as unfriendly to that as an algorithm can be. Its first probes jump half the array, then a quarter, then an eighth. Each one lands on a different cache line, often a different memory page, and there’s no pattern the hardware can prefetch. Only the last few probes, when the range has shrunk to a few cache lines, are cheap.

I measured it in C on my laptop (M1 Pro, cc -O2), 4 million random lookups per array size. The left column is the textbook loop on a sorted array. The right column is the same keys stored in a different order, described below:

Going from a thousand elements to 268 million adds 18 comparisons to each lookup (10 become 28), 2.8 times as many, and the time grows 75 times. The comparisons didn’t get slower. The memory did: once the array outgrows the caches, most probes wait for RAM. Timings at the large sizes moved a lot between runs (a second run measured 1,879 ns for the sorted gigabyte), but the gap between the columns was there every time.

The fix is to store the keys in the order the search visits them. Picture the sorted array as the binary tree that binary search walks: the middle element is the root, the quarter points are its children, and so on. The Eytzinger layout, named after a 16th-century genealogist’s numbering of family trees, stores that tree level by level: root at slot 1, its children at 2 and 3, theirs at 4 to 7, and the children of slot k at 2k and 2k + 1.

Now the top levels of the tree, which every single lookup reads, sit together at the front of the array and stay in cache. And the descent from slot k only ever goes to 2k or 2k + 1, so the four levels below the current one sit in a contiguous run that the code can ask the CPU to fetch early, before it knows which way it will turn. The search loop is tiny:

static int eytz_lower_bound(const int *e, int n, int x) {
    int k = 1;
    while (k <= n) {
        __builtin_prefetch(e + k * 16);     // the four levels below are in one or two cache lines
        k = 2 * k + (e[k] < x);
    }
    k >>= __builtin_ffs(~k);                // undo the final run of right turns
    return k;
}

k = 2 * k + (e[k] < x) has no if, which also helps: the CPU can’t predict which way a binary search will go, and every wrong guess costs it a pipeline flush. Paul-Virak Khuong and Pat Morin studied these layouts carefully in “Array Layouts for Comparison-Based Searching” and found an Eytzinger layout with prefetching the fastest of the options they tried for large arrays. The other well-known answer is to put several keys in each node so one cache line answers several levels at once. That’s a B-tree, and it’s where the Expert section starts.

Should you do this in your service? Almost never by hand. If you search a sorted array of a few thousand items, it sits in cache and the textbook loop is fine. If you search hundreds of megabytes of sorted keys in a hot loop, you’re building an index, and you should know the layout matters by a factor of several.

Galloping: exponential search

Sometimes the answer is probably near the start: you’re merging two sorted lists, or scanning a log from the last position you remember. A full binary search spends log₂ n comparisons even when the answer is at position 3. Exponential search, also called galloping, checks positions 1, 2, 4, 8, … until it passes the target, then binary searches inside the last jump:

def exponential_search(a, x):
    """Lower bound of x, plus how many comparisons it took. Cheap when the answer is near the front."""
    comparisons = 0
    bound = 1
    while bound <= len(a):                      # probe a[0], a[1], a[3], a[7], ... until we pass x
        comparisons += 1
        if a[bound - 1] >= x:
            break
        bound *= 2
    lo, hi = bound // 2, min(bound - 1, len(a))  # the answer is in [lo, hi]
    while lo < hi:                               # an ordinary lower bound on that slice
        comparisons += 1
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo, comparisons

from bisect import bisect_left
a = list(range(0, 2_000_000, 2))                # a million sorted even numbers
for x in (0, 7, 101, 20_001, 1_999_999, 5_000_000):
    pos, cost = exponential_search(a, x)
    assert pos == bisect_left(a, x)
    print(f"x={x:>9,}: position {pos:>9,}, {cost:>2} comparisons")
# x=        0: position         0,  1 comparisons
# x=        7: position         4,  6 comparisons
# x=      101: position        51, 12 comparisons
# x=   20,001: position    10,001, 28 comparisons
# x=1,999,999: position 1,000,000, 38 comparisons
# x=5,000,000: position 1,000,000, 38 comparisons

The cost is about 2 × log₂(position) instead of log₂(n): six comparisons to find position 4 in a million, where plain binary search always spends 20. In exchange, the worst case is about twice binary search’s. It’s the right tool when the answer is usually close, and it’s the only tool when you don’t know n at all (the Advanced exercise below).

Python’s own sort uses it. Timsort finds runs that are already in order and merges them, and its notes (Objects/listsort.txt in CPython) describe galloping mode: when one run wins MIN_GALLOP = 7 comparisons in a row during a merge, the merge stops comparing one element at a time and gallops, comparing against positions 1, 3, 7, 15 and so on, then binary searching. You can count the effect:

import random

class Counted:
    """An int that counts how often sort compares it."""
    comparisons = 0
    __slots__ = ("v",)
    def __init__(self, v):
        self.v = v
    def __lt__(self, other):
        Counted.comparisons += 1
        return self.v < other.v

def comparisons_to_sort(values):
    items = [Counted(v) for v in values]
    Counted.comparisons = 0
    items.sort()
    return Counted.comparisons

n = 100_000
random.seed(2)
cases = {
    "two runs, one after the other": list(range(n, 2 * n)) + list(range(n)),
    "two runs, interleaved values": list(range(0, 2 * n, 2)) + list(range(1, 2 * n, 2)),
    "random order": random.sample(range(2 * n), 2 * n),
}
for name, values in cases.items():
    print(f"{name:<30} {comparisons_to_sort(values):>9,} comparisons for {2 * n:,} items")
# two runs, one after the other    200,042 comparisons for 200,000 items
# two runs, interleaved values     399,999 comparisons for 200,000 items
# random order                   3,263,368 comparisons for 200,000 items

Finding the two runs costs 199,999 comparisons in both run cases (I checked by sorting each run alone). So in the first case the merge itself took 43 comparisons for 200,000 items: galloping discovered that one whole run belongs after the other in a few dozen probes. In the interleaved case the runs alternate on every element, galloping never pays, and the merge does one comparison per element, about 200,000. Same algorithm, same size, and a factor of 4,600 in merge work, depending only on how the data is arranged.

What each language gives you

Two notes. Java and Rust don’t promise which match you get when there are duplicates; if you need the first one, use a bound. And Go’s sort.Search is the cleanest API in the table, because it’s literally the monotonic predicate: its doc comment says it returns “the smallest index i in [0, n) at which f(i) is true, assuming that on the range [0, n), f(i) == true implies f(i+1) == true.” That’s first_true, in the standard library.

class Stream:
    """A sorted sequence you can index but not measure, like pages of an API with no total."""
    def __init__(self, values):
        self._values = values
        self.reads = 0
    def get(self, i):
        self.reads += 1
        return self._values[i] if i < len(self._values) else None   # None: past the end

def find_in_stream(s, x):
    hi = 1
    while (v := s.get(hi)) is not None and v < x:   # gallop until we pass x or the end
        hi *= 2
    lo = hi // 2
    while lo < hi:                                   # lower bound in [lo, hi); None counts as +infinity
        mid = (lo + hi) // 2
        v = s.get(mid)
        if v is not None and v < x:
            lo = mid + 1
        else:
            hi = mid
    v = s.get(lo)
    return lo if v == x else -1

s = Stream(list(range(0, 3_000_000, 3)))            # a million values, length unknown to the caller
print(find_in_stream(s, 2_999_997), s.reads)
s.reads = 0
print(find_in_stream(s, 30), s.reads)
s.reads = 0
print(find_in_stream(s, 31), s.reads)
# 999999 41
# 10 9
# -1 9

def cube_root(x, iterations=200):
    lo, hi = min(-1.0, x), max(1.0, x)                # the root of any x lies in here
    for _ in range(iterations):
        mid = (lo + hi) / 2
        if mid ** 3 < x:
            lo = mid
        else:
            hi = mid
    return hi

print(cube_root(27), cube_root(-8), cube_root(2), cube_root(0.001), cube_root(1e30))
# 3.0 -2.0 1.2599210498948732 0.1 10000000000.0

Expert: B-trees, bisecting history and the predicate underneath

At this level binary search stops being a loop over an array and becomes a way of thinking: about storage, where the expensive step is a page read; about debugging, where the expensive step is a build and a test; and about any question whose answer flips exactly once.

How does PostgreSQL find one row in ten million?

It walks a B-tree, a tree whose nodes are whole disk pages packed with sorted keys, and does a binary search inside each page. To see the numbers instead of describing them, I built a table of 10 million rows on my laptop (PostgreSQL 14), added a primary key on id, and looked at the index with the pageinspect extension:

SELECT btpo_level AS level, type, count(*) AS pages, round(avg(live_items)) AS avg_entries
FROM generate_series(1, pg_relation_size('orders_pkey') / 8192 - 1) AS b,
     LATERAL bt_page_stats('orders_pkey', b::int)
GROUP BY btpo_level, type ORDER BY level DESC;
--  level | type | pages | avg_entries
-- -------+------+-------+-------------
--      2 | r    |     1 |          97
--      1 | i    |    97 |         283
--      0 | l    | 27323 |         367

One root page with 97 entries, 97 internal pages with about 283 each, and 27,323 leaf pages holding about 366 ids each (the 367 includes one “high key” per leaf, a copy of the boundary used to navigate). The table itself is 574 MB and the index 214 MB, in 8 KB pages. Then a lookup, run twice so the pages were already in memory:

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF) SELECT * FROM orders WHERE id = 7654321;
--  Index Scan using orders_pkey on orders (actual rows=1 loops=1)
--    Index Cond: (id = 7654321)
--    Buffers: shared hit=4
--  Planning Time: 0.014 ms
--  Execution Time: 0.005 ms

Four pages: the root, one internal page, one leaf, and the table page holding the row. Without the index, the same query read all 73,432 pages of the table in a parallel sequential scan, which took between 0.2 and 3 seconds across my runs depending on how much of the table the operating system had cached.

Here’s the part that connects back to the Advanced section. Count comparisons instead of pages: a binary search over 97 keys takes about 7, over 283 about 8, over 367 about 9. That’s 24 comparisons, which is the same as binary searching all 10 million ids directly (log₂ 10,000,000 ≈ 23.3). A B-tree doesn’t do fewer comparisons than binary search. It groups them so that each memory or disk fetch answers seven to nine of them at once. A plain binary search over the same ids laid out in 27,000 sorted pages would touch about 15 different pages before the range shrank to one.

PostgreSQL’s source says the per-page search outright. _bt_binsrch in nbtsearch.c is described as “Do a binary search for a key on a particular page”, and on a leaf page it “returns the OffsetNumber of the first key >= given scankey, or > scankey if nextkey is true”. That’s lower bound and upper bound, the two functions from Intermediate, at the bottom of every index lookup in the database.

The Advanced section’s other fix shows up too. The tree is shallow because each node is wide: 283 children per internal page means three levels cover 10 million rows and four would cover billions. The depth grows with log base 283 of n, not log base 2.

Two more properties matter in production:

• Leaves are linked in key order. Once the descent finds the first matching key, a range query (WHERE created_at > ..., ORDER BY ... LIMIT 50) walks sideways through the leaves without going back up. That’s why an index can return the first 50 rows of a sorted result without sorting anything.
• Concurrency. PostgreSQL’s B-tree README opens by saying it’s “a correct implementation of Lehman and Yao’s high-concurrency B-tree management algorithm”, from a 1981 paper. Each page has a link to its right sibling. If a page splits while a reader is descending towards it, the reader notices its key is beyond the page’s high key and follows the right-link, instead of holding locks on the whole path. A binary search over a shared array has no answer to a concurrent insert; a B-tree was designed for one.

The predicate is the real algorithm

Strip binary search down and one requirement is left: a yes/no question over an ordered range whose answer flips at most once. Sorted arrays are just the case where the question is “is a[i] at least x?”. Everything in this article, bounds, ship capacities, rotated arrays, square roots, B-tree pages, is that question in a different form.

That framing also tells you when binary search is the wrong tool. If the predicate can flip back, binary search will confidently return a wrong answer, because it never looks at the parts it discarded. A test that fails intermittently, a performance metric that’s noisy, a “sorted” list that isn’t sorted by the rule you compare with: all break the one requirement, and none of them raise an error.

It also explains why the cleverer-sounding alternative is a risk. Interpolation search guesses the position from the values, like opening a phone book near “S” for “Smith”. On evenly spread data it needs about log log n probes. On skewed data it can degrade towards a linear scan:

import random

def interpolation_probes(a, x):
    """Guess the position from the values, like opening a phone book near the right letter."""
    lo, hi, probes = 0, len(a) - 1, 0
    while lo <= hi and a[lo] <= x <= a[hi]:
        probes += 1
        if a[hi] == a[lo]:
            pos = lo
        else:
            pos = lo + (x - a[lo]) * (hi - lo) // (a[hi] - a[lo])
        if a[pos] == x:
            return probes
        if a[pos] < x:
            lo = pos + 1
        else:
            hi = pos - 1
    return probes

def binary_probes(a, x):
    lo, hi, probes = 0, len(a) - 1, 0
    while lo <= hi:
        probes += 1
        mid = (lo + hi) // 2
        if a[mid] == x:
            return probes
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return probes

random.seed(4)
n = 1_000_000
uniform = sorted(random.sample(range(100 * n), n))
skewed = [2 ** i for i in range(60)] + list(range(2 ** 60, 2 ** 60 + n - 60))  # a few huge gaps
for name, a in (("uniform", uniform), ("skewed", skewed)):
    targets = random.sample(a, 1_000)
    worst_i = max(interpolation_probes(a, t) for t in targets)
    worst_b = max(binary_probes(a, t) for t in targets)
    print(f"{name:>8}: interpolation worst {worst_i:>7,} probes, binary worst {worst_b} probes")
#  uniform: interpolation worst      10 probes, binary worst 20 probes
#   skewed: interpolation worst 499,530 probes, binary worst 20 probes

Sixty values with enormous gaps between them were enough to wreck it. If an attacker or just an odd tenant controls the keys, binary search’s guarantee, never more than log₂ n + 1 probes whatever the data, is worth more than interpolation’s best case. The research version of the same bet is the learned index (Kraska and colleagues, “The Case for Learned Index Structures”, 2018): fit a model that predicts a key’s position, then binary search a small window around the prediction to correct its error. The binary search is the safety net that makes the guess safe to use.

git bisect: binary search over history

A test passes on last month’s release and fails today, with a thousand commits in between. The commits are ordered, and “is this commit broken?” goes False, False, …, True, True if the bug arrived once and stayed. That’s a first-true search, and git has it built in:

$ git bisect start HEAD <first-commit>      # bad, then good
Bisecting: 499 revisions left to test after this (roughly 9 steps)
[<sha>] change 500
$ git bisect run ./test.sh                  # exit 0 = good, 1-127 = bad, 125 = can't test, skip it
Bisecting: 249 revisions left to test after this (roughly 8 steps)
Bisecting: 124 revisions left to test after this (roughly 7 steps)
Bisecting: 62 revisions left to test after this (roughly 6 steps)
Bisecting: 31 revisions left to test after this (roughly 5 steps)
Bisecting: 15 revisions left to test after this (roughly 4 steps)
Bisecting: 7 revisions left to test after this (roughly 3 steps)
Bisecting: 3 revisions left to test after this (roughly 2 steps)
Bisecting: 1 revision left to test after this (roughly 1 step)
Bisecting: 0 revisions left to test after this (roughly 0 steps)
<sha> is the first bad commit
    change 613

That’s a throwaway repository I built for this article: 1,000 commits, where commit 613 changed round(p * 1.06, 2) to int(p * 1.06), and a one-line test asserting total(10) == 10.6. git bisect run checked out ten commits and ran the test on each. Ten builds instead of up to a thousand.

Three things decide whether bisecting works in practice:

1. The test must be deterministic. One flaky failure marks a good commit bad, and the search confidently narrows to the wrong half. If a test is flaky, make the script run it several times and fail only if it fails consistently, or fix the flake first.
2. Some commits can’t be tested. A commit that doesn’t build says nothing about the bug. Exit code 125 from the script (or git bisect skip by hand) tells git to try a neighbor instead.
3. Each step’s cost multiplies. Ten steps of a two-minute test is twenty minutes. Ten steps of a full integration suite is an afternoon. Make the test as narrow as the bug.

Bisecting configuration and deploys

The same move works on anything you can order and test. Forty configuration changes went out together and something broke: apply the first twenty and test. A release range between a good deploy and a bad one: deploy the midpoint to a staging environment and test. Each step halves the suspects, so forty changes take about six tests and a thousand deploys take ten.

The thing to watch is the predicate. Prefix bisection (“apply the first k changes”) finds the change that completes the failure, which is exactly the culprit when one change is at fault. When two changes only break together, it finds the second of them, and the first stays hidden. The Expert exercise below shows that happening. If you suspect an interaction, the generalization is delta debugging (Andreas Zeller’s ddmin algorithm), which searches subsets rather than prefixes to find a minimal failing set.

And in production the cheapest bisection step is often not a test at all. If you deploy small changes behind feature flags, turning one flag off is a search step that takes seconds. Small, separately revertible changes are what make bisection cheap.

k-ary and parallel search

Binary search asks one question per step because it has one place to look. With p workers that can check at once, split the range into p + 1 parts instead of 2 and check all the dividing points together. Each round keeps one part out of p + 1, so the number of rounds is log base (p + 1) of n. With three CI machines bisecting a thousand commits, that’s 5 rounds instead of 10. Diminishing returns arrive fast: going from 1 worker to 3 halves the rounds, and going from 3 to 15 only halves them again.

Hardware does the same thing at a smaller scale. A SIMD instruction can compare one key against 4, 8 or 16 keys in a single step, and k-ary search on modern processors (Schlegel, Gemulla and Lehner, 2009) and FAST (Kim and colleagues, SIGMOD 2010) lay trees out so that each step is one such instruction over one cache line. A B-tree page is the disk version of the same idea. The general pattern: when a step is expensive and checking several points costs about the same as checking one, widen the step.

Reviewing a binary search in a design

When binary search, a sorted index or a bisection procedure appears in a design or a code review, these are the questions I ask:

• What’s the predicate, and is it really monotonic? Name it in one sentence. If it’s “the test fails”, is the test deterministic? If it’s “the list is sorted”, sorted by what, and who guarantees it stays sorted?
• What do the boundaries mean, and what’s returned when nothing matches? -1, len(a), None, an exception. Each caller has to handle it.
• Duplicates: first, last or any? Most library exact-match functions return any match.
• Where does the sorted order come from, and what does it cost to keep? Sorting once is fine; insort in a loop is quadratic; a database index costs a write on every insert.
• What’s the expensive step? Comparisons, cache misses, page reads, builds, deploys. Optimize the count of those, not the count of loop iterations.
• At large n, what’s the integer type? lo + (hi - lo) / 2 in any fixed-width language.

def culprit(changes, breaks):
    """changes: in the order they were applied. breaks(prefix): one test run with only
    those changes applied. Assumes the empty prefix works and the full list breaks."""
    lo, hi, runs = 1, len(changes), 0       # the answer k is the shortest breaking prefix
    while lo < hi:
        mid = (lo + hi) // 2
        runs += 1
        if breaks(changes[:mid]):
            hi = mid                        # breaks with mid changes: culprit is among them
        else:
            lo = mid + 1                    # still fine: culprit comes later
    return changes[lo - 1], runs

flags = [f"flag_{i:02}" for i in range(40)]
print(culprit(flags, lambda on: "flag_27" in on))
print(culprit(flags, lambda on: "flag_00" in on), culprit(flags, lambda on: "flag_39" in on))

# Two flags that only break together: the predicate is still monotone in the prefix.
print(culprit(flags, lambda on: "flag_05" in on and "flag_31" in on))
# ('flag_27', 5)
# ('flag_00', 6) ('flag_39', 5)
# ('flag_31', 6)

In production: sorted order in ezychat.io

I’m the primary engineer of ezychat.io, a multi-tenant platform where AI and people answer customers on WhatsApp, Instagram, Messenger and web chat. It’s Python (FastAPI and Celery), PostgreSQL and Redis, and production AI runs on Gemini. Here’s an honest inventory of binary search in it: the backend never imports bisect, and nowhere does it hand-write the loop. What it does have is a lot of decisions that only make sense if you think in sorted order, and nearly all of them are about PostgreSQL’s B-tree indexes. These are trimmed excerpts from the codebase, its migrations and its handbook.

The one “bisect” in the code

Search the backend for “bisect” and you get one hit, a comment in the module that writes public replies to social media comments:

# A public reply is read by people scrolling. Long is not more helpful here;
# it is less read. Enforced after citation extraction, never before — a marker
# bisected by truncation loses its closing bracket and survives every pattern
# that would have removed it.
PUBLIC_REPLY_MAX_CHARS = 500

That’s “bisected” in its everyday sense, cut in two, and it’s about ordering operations, not searching. Citation markers like [chunk:ID] are stripped from the model’s draft by pattern matching. If the 500-character cap ran first, it could cut a marker in half, [chunk:ab with no closing bracket, and no pattern would match the half, so the fragment would be published. The code extracts citations first and truncates afterwards. I mention it so nobody greps the codebase, finds the word, and assumes it’s a binary search.

A lower bound, written as a scan

The closest thing to bisect in the backend is the client-happiness feature, which turns a deal room’s rolling score into a colored band. Bands are defined by ceilings: the defaults are Green with no ceiling, Yellow up to −1 and Red up to −6, and each organization can change them. Finding a score’s band is this:

def band_for_score(bands: list[models.HappinessFlagBand], score: int) -> models.HappinessFlagBand:
    """The band a rolling score falls into: the lowest ceiling still at or
    above it, with an open ceiling counting as infinity.

    Lives here rather than in the scoring engine because the dashboard, the
    room panel, and the settings preview all need the same answer and a second
    implementation would eventually disagree with the first about a boundary.
    """
    eligible = [b for b in bands if b.max_score is None or b.max_score >= score]
    return min(eligible, key=lambda b: (b.max_score is None, b.max_score or 0, b.rank))

“The lowest ceiling still at or above it” is the definition of a lower bound, the grade-bands pattern from Intermediate, written as a filter and a min. To check that reading, I rewrote it with bisect_left and compared the two on every score from −50 to 50:

from bisect import bisect_left
from dataclasses import dataclass

@dataclass
class Band:
    rank: int
    name: str
    max_score: int | None           # a ceiling; None means open at the top

def band_for_score(bands, score):   # the production rule, as written
    eligible = [b for b in bands if b.max_score is None or b.max_score >= score]
    return min(eligible, key=lambda b: (b.max_score is None, b.max_score or 0, b.rank))

def band_for_score_bisect(bands, score):
    """The same question as a lower bound: the first ceiling >= score."""
    ordered = sorted(bands, key=lambda b: (b.max_score is None, b.max_score or 0, b.rank))
    ceilings = [float("inf") if b.max_score is None else b.max_score for b in ordered]
    return ordered[bisect_left(ceilings, score)]

defaults = [Band(0, "Green", None), Band(1, "Yellow", -1), Band(2, "Red", -6)]
print([band_for_score(defaults, s).name for s in (3, 0, -1, -5, -6, -20)])
assert all(band_for_score(defaults, s) is band_for_score_bisect(defaults, s) for s in range(-50, 51))
print("same band for every score from -50 to 50")
# ['Green', 'Green', 'Yellow', 'Yellow', 'Red', 'Red']
# same band for every score from -50 to 50

They agree, and the scan is the right choice. The settings API caps an organization at MAX_BANDS = 8, so the scan does at most eight comparisons. The function also doesn’t assume its input is sorted, so a bisect version would have to sort the bands first and would do more work, not less. The docstring’s real concern is in its second paragraph: one implementation, so the dashboard and the settings preview can never disagree about a boundary. Boundary agreement (is a score of exactly −1 Yellow or Green?) is the thing worth protecting here, and >= against the ceiling settles it. If bands ever numbered in the thousands and were looked up in a hot loop, I’d sort them once and keep the ceilings list. At eight, I wouldn’t touch it.

Keyset pagination is a B-tree seek

ezychat’s list endpoints (members, conversations, messages, leads, the comment feed) page with a cursor, not an offset. The architecture decision record, ADR-0005, rejects OFFSET because “Cost grows linearly with page depth (OFFSET 10000 scans and discards 10,000 rows); unstable under concurrent inserts”. The inbox list does this instead:

if cursor:
    ts, cursor_id = parse_datetime_cursor(cursor)
    stmt = stmt.where(
        or_(
            Conversation.last_message_at < ts,
            and_(Conversation.last_message_at == ts, Conversation.id < cursor_id),
        )
    )
stmt = stmt.order_by(Conversation.last_message_at.desc(), Conversation.id.desc()).limit(
    limit + 1
)

The cursor is the sort key of the last row on the previous page. “Rows after this one, in this order” is a lower-bound question, and with an index on (org_id, last_message_at DESC, id DESC) PostgreSQL answers it the way the Expert section showed: descend the tree to the first entry past the cursor, then walk the linked leaves for limit + 1 entries and stop. Page 1 and page 400 cost the same. The extra row is how has_more is computed without a COUNT(*).

The id in the cursor is what makes it correct, and the comment feed’s migration (0107) measured what happens without it in the index. The feed’s cursor was already (last_activity_at DESC, id DESC), but the index stopped at (org_id, last_activity_at DESC), so PostgreSQL had to sort each group of equal timestamps by id itself. Against 50,000 seeded threads plus a 5,000-thread burst sharing one instant, “which is what a post going viral looks like”, the first page read 5,001 rows in 2.455 ms. With the index matching the cursor exactly, it read 50 rows in 0.953 ms, with no sort step in the plan. The migration’s summary is the lesson: “The difference is not the milliseconds, it is the shape: O(tie group) becomes O(page).”

In binary search terms: a timestamp alone isn’t a total order, because many rows can share it. A lower bound on a non-unique key lands at the start of a run of duplicates, and the next page has to know where inside that run to resume. Adding id makes every key unique, so “the first entry after the cursor” is one exact position in the tree.

The index whose second column broke the order

The most expensive statement on the platform during the August load test was the inbox list. The migration that fixed it (0085) recorded it at 142 ms mean, with 52.9 seconds of database time in a 25-second run, “more than the next nine statements combined.” There was an index starting with the right column:

CREATE INDEX IF NOT EXISTS ix_conversations_org_status_last_msg
    ON conversations (org_id, status, last_message_at DESC, id DESC)

But the inbox doesn’t filter on status. A B-tree is one sorted list of its whole key, compared column by column, so inside one organization the entries are ordered by status first, and by time only within each status. “Newest 50 across all statuses” isn’t a contiguous run anywhere in that list.

So PostgreSQL did the only thing it could. It read all 220,000 of the largest tenant’s conversations and sorted them on disk (Sort Method: external merge Disk: 3872kB) to return 50 rows. The fix was the index the query’s order actually needed:

_READ_PATH: list[tuple[str, str, str]] = [
    ("ix_conversations_org_last_msg", "conversations", "org_id, last_message_at DESC, id DESC"),
]

310 ms became 12.9 ms, and the disk sort disappeared. Together with the contacts list fix in the same migration, throughput across the whole scenario mix went from 35.4 to 70.4 requests per second, and median latency from 349 ms to 121 ms. The migration states the general rule better than I can: “an index whose second column is an equality column the query does not constrain cannot satisfy that query’s ORDER BY.” The old index stayed, because the status-filtered inbox still uses it.

The orders module’s handbook records the same lesson with an inequality: ix_sales_orders_org_status “cannot sort past the status <> 'draft' inequality”, so the CSV export’s paged reads were a parallel sequential scan and a top-N sort, 41 ms a page, until a partial index on (org_id, created_at, id) WHERE status <> 'draft' took the inequality out of the key and made each page a seek at 0.7 ms. A range or inequality on one column scatters the order of every column after it; a partial index’s WHERE is one way to get it out of the way.

57 foreign keys and a delete that never finished

PostgreSQL indexes a primary key automatically. It does nothing for the column that points at a primary key. Delete a contact, and PostgreSQL must check every table that references contacts for rows pointing at it; without an index on the referencing column, each check is a sequential scan.

The same migration found 86 foreign keys like that. It surfaced as “a purge of 120,000 seeded contacts that ran for 3 minutes 42 seconds and was still going when it was cancelled; with conversations emptied first the same delete took 4.5 s.” One scan of the conversation history per contact removed. And deleting a contact isn’t a cleanup job: it’s how the product honors a data-erasure request under Malaysia’s PDPA, so its cost mattered.

The fix added 57 indexes, each a bare column, and the reason they’re bare is a sorted-order argument. Every other index in the schema leads with org_id, because every query is tenant-scoped. These can’t: PostgreSQL checks a foreign key with WHERE <fk_column> = $1 and no tenant predicate, and an index on (org_id, contact_id) is sorted by org_id first, so a search on contact_id alone can’t use it. The migration’s draft hit a subtler version of this: CREATE INDEX IF NOT EXISTS ix_leads_contact “silently did nothing”, because an index with that name already existed on (org_id, contact_id) and the check matches names, not definitions. Hence the _fk suffix on every new index.

The foreign keys that stayed unindexed were left out on purpose, and the reasons are written down. Three columns on conversations are exempt because that table “takes an UPDATE on every inbound message, so each extra index is a write cost on the hottest path in the product”, and the bare org_id foreign keys are exempt as a class because deleting a whole organization is a rare manual job, not a request path. A test now fails the suite for any new unindexed foreign key unless it’s added to the exemption list with a reason. That’s the cost from Intermediate, keeping data sorted is paid on every write, turned into a rule a reviewer can see.

What a B-tree can’t do: search inside a string

The contacts directory searches names, emails and phone numbers with ILIKE '%x%', a substring match. The handbook notes that the existing B-tree indexes on email and phone “serve only equality and prefix, not the substring match the UI performs”, so the module added trigram (pg_trgm) GIN indexes instead, and the deal-rooms list did the same.

That limit falls straight out of sorted order. Every string that starts with “tar” sits in one contiguous run of a sorted list, between “tar” and “tas”, so a prefix search is two bounds and a range scan. Strings that contain “tar” are scattered all over the list, and no binary search can find them without looking at everything. A trigram index answers a different question, which three-letter fragments a string contains, and that one has an index-shaped answer.

What production adds to the textbook

• In a database, the binary search is the index. Nobody in this backend writes the loop; they choose which columns, in which order, so that the question a query asks is a contiguous range in some B-tree. Every fix above was making the index order match the query’s filter and sort.
• Equality columns first, then the order you sort by, then a unique tie-break. An unconstrained column or an inequality early in the index breaks the order of everything after it.
• Make the key unique before you page on it. A lower bound on duplicate timestamps lands in the middle of a crowd; adding id turns “after this cursor” into one position.
• Sorted order costs writes. Each index is maintained on every insert and update, so the hottest table gets the fewest indexes, and the decision is written down where a test enforces it.
• For eight items, scan. The band lookup is a lower bound, and a list comprehension is the right way to compute it.

Cheat sheet