Binary search: invariants and implementation

Binary search answers “is this value in the sorted array, and where?” by looking at the middle element and discarding the half that cannot contain the value. Every look, or probe, halves what is left, so a million sorted values need at most 20 probes and a billion need at most 30, where a scan from the front may have to read every value. The idea fits in two sentences, yet first attempts often loop for ever or miss a value that is there. The cure is to write down one invariant and let it choose every boundary. This lesson builds the classic version on a closed range from that invariant, traces it on real data, proves that it stops, measures its probe count for every size up to about a million, and catches the three slips and the overflow that break most first versions.

The idea: keep only the half that can hold the value

An exam hall has a list of 16 roll numbers, sorted from smallest to largest, and you want to know whether roll number 200 is on it. Reading from the top works, but it may take 16 looks. Instead, look at the middle of the list. It holds 178, which is smaller than 200, and because the list is sorted, everything before it is smaller still. One comparison has ruled out half the list, and the same move works again on the half that is left.

Two things make this work. The data must be sorted, so that one comparison tells you which side the value would be on. And the program must reach any position in one step: a Python list or an array can, a linked list cannot, because it has to walk to the middle first. When either is missing, binary search is the wrong tool.

The invariant behind lo, mid and hi

The program keeps two positions, lo and hi, and promises one thing about them:

Invariant: if the target is anywhere in a, it is in a[lo..hi], both ends included.

This is a closed range. It starts as the whole array, lo = 0 and hi = len(a) - 1, so the invariant holds before the first probe: if the target is in the array at all, it is somewhere between the first and the last position.

Each probe reads the middle position, mid, and keeps the promise in each of the three cases:

• a[mid] == target: the search is over, and mid is the answer.
• a[mid] < target: the array is sorted, so every value at positions lo to mid is below the target. The target, if it is there, must be to the right: lo = mid + 1.
• a[mid] > target: by the same argument everything from mid to hi is above it, so hi = mid - 1.

The + 1 and - 1 are not decoration. The value at mid has already been compared, so leaving it out loses nothing, and leaving it out is what makes the range smaller on every probe.

The loop runs while lo <= hi, that is, while the range still holds at least one position. When it stops without finding the target, lo has passed hi, the range is empty, and the invariant says the target is in no position at all: the right answer is −1.

A traced run you can change

This program prints lo, hi and mid at every probe of two searches over the roll numbers. Press Edit, put other targets in TARGETS, and run it again:

# A traced binary search over a sorted list of roll numbers. Each line is one probe: the range [lo, hi] still in
# doubt, the middle position and what the comparison decided. Press Edit, change TARGETS, and run it again.

ROLLS = [103, 117, 122, 135, 141, 156, 162, 178, 184, 190, 207, 213, 229, 236, 248, 251]
TARGETS = [141, 200]


def traced_search(a, target):
    lo, hi = 0, len(a) - 1          # invariant: if target is in a, it is in a[lo..hi]
    probe = 0
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        probe += 1
        if a[mid] == target:
            print(f"  probe {probe}: lo={lo:2} hi={hi:2} mid={mid:2} a[mid]={a[mid]}  found")
            return mid
        if a[mid] < target:
            print(f"  probe {probe}: lo={lo:2} hi={hi:2} mid={mid:2} a[mid]={a[mid]}  too small: lo = {mid + 1}")
            lo = mid + 1
        else:
            print(f"  probe {probe}: lo={lo:2} hi={hi:2} mid={mid:2} a[mid]={a[mid]}  too big:   hi = {mid - 1}")
            hi = mid - 1
    print(f"  lo={lo} > hi={hi}: the range is empty")
    return -1


for target in TARGETS:
    print(f"search for {target} in {len(ROLLS)} roll numbers")
    print(f"  -> {traced_search(ROLLS, target)}")

search for 141 in 16 roll numbers
  probe 1: lo= 0 hi=15 mid= 7 a[mid]=178  too big:   hi = 6
  probe 2: lo= 0 hi= 6 mid= 3 a[mid]=135  too small: lo = 4
  probe 3: lo= 4 hi= 6 mid= 5 a[mid]=156  too big:   hi = 4
  probe 4: lo= 4 hi= 4 mid= 4 a[mid]=141  found
  -> 4
search for 200 in 16 roll numbers
  probe 1: lo= 0 hi=15 mid= 7 a[mid]=178  too small: lo = 8
  probe 2: lo= 8 hi=15 mid=11 a[mid]=213  too big:   hi = 10
  probe 3: lo= 8 hi=10 mid= 9 a[mid]=190  too small: lo = 10
  probe 4: lo=10 hi=10 mid=10 a[mid]=207  too big:   hi = 9
  lo=10 > hi=9: the range is empty
  -> -1

The search for 141 finds it on the fourth probe, when the range has narrowed to position 4 alone. The search for 200 narrows the range the same way until it holds only position 10, where 207 sits. That value is too big, so hi becomes 9, lo is 10, and the empty range proves that 200 is absent. Try 103 and 251, the first and last values, then 99 and 300, which lie outside the list: the last two are the cases where a slip in the code usually shows.

The same search in five languages

The loop translates line for line. Each version below searches the roll numbers for 141, 200 and 300, then computes the midpoint of two large bounds, 1,500,000,000 and 2,000,000,000, in more than one way:

# Iterative binary search on the closed range [lo, hi], with a probe counter, then the midpoint of two large bounds.


def binary_search(a, target):
    """Index of target in the sorted list a, or -1, and the number of probes it took."""
    lo, hi = 0, len(a) - 1          # invariant: if target is in a, it is in a[lo..hi]
    probes = 0
    while lo <= hi:                 # the range is not empty
        mid = lo + (hi - lo) // 2
        probes += 1
        if a[mid] == target:
            return mid, probes
        if a[mid] < target:
            lo = mid + 1            # a[lo..mid] are all below target
        else:
            hi = mid - 1            # a[mid..hi] are all above target
    return -1, probes


ROLLS = [103, 117, 122, 135, 141, 156, 162, 178, 184, 190, 207, 213, 229, 236, 248, 251]
for target in (141, 200, 300):
    index, probes = binary_search(ROLLS, target)
    print(f"{target}: index {index}, {probes} probes")

lo, hi = 1_500_000_000, 2_000_000_000
print("(lo + hi) // 2      =", (lo + hi) // 2)
print("lo + (hi - lo) // 2 =", lo + (hi - lo) // 2)

141: index 4, 4 probes
200: index -1, 4 probes
300: index -1, 5 probes
(lo + hi) // 2      = 1750000000
lo + (hi - lo) // 2 = 1750000000

// Iterative binary search on the closed range [lo, hi], with a probe counter, then the midpoint of two large bounds.

function binarySearch(a, target) {
  let lo = 0;
  let hi = a.length - 1; // invariant: if target is in a, it is in a[lo..hi]
  let probes = 0;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    probes++;
    if (a[mid] === target) return [mid, probes];
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return [-1, probes];
}

const ROLLS = [103, 117, 122, 135, 141, 156, 162, 178, 184, 190, 207, 213, 229, 236, 248, 251];
for (const target of [141, 200, 300]) {
  const [index, probes] = binarySearch(ROLLS, target);
  console.log(`${target}: index ${index}, ${probes} probes`);
}

const lo = 1_500_000_000;
const hi = 2_000_000_000;
// Numbers are 64-bit floats, exact up to 2 ** 53, so the sum itself is fine here.
console.log('Math.floor((lo + hi) / 2) =', Math.floor((lo + hi) / 2));
// | 0 converts to a 32-bit integer (ToInt32), which is what Java's int addition would have produced.
console.log('((lo + hi) | 0) >> 1      =', ((lo + hi) | 0) >> 1);
console.log('lo + ((hi - lo) >> 1)     =', lo + ((hi - lo) >> 1));

141: index 4, 4 probes
200: index -1, 4 probes
300: index -1, 5 probes
Math.floor((lo + hi) / 2) = 1750000000
((lo + hi) | 0) >> 1      = -397483648
lo + ((hi - lo) >> 1)     = 1750000000

// Iterative binary search on the closed range [lo, hi], with a probe counter, then the midpoint of two large bounds.
public class BinarySearch {
    static int probes;

    /** Index of target in the sorted array a, or -1; the probes it took are left in `probes`. */
    static int binarySearch(int[] a, int target) {
        int lo = 0, hi = a.length - 1; // invariant: if target is in a, it is in a[lo..hi]
        probes = 0;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            probes++;
            if (a[mid] == target) return mid;
            if (a[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] rolls = {103, 117, 122, 135, 141, 156, 162, 178, 184, 190, 207, 213, 229, 236, 248, 251};
        for (int target : new int[] {141, 200, 300}) {
            int index = binarySearch(rolls, target);
            System.out.println(target + ": index " + index + ", " + probes + " probes");
        }
        int lo = 1_500_000_000, hi = 2_000_000_000;
        System.out.println("lo + (hi - lo) / 2 = " + (lo + (hi - lo) / 2));
        System.out.println("(lo + hi) >>> 1    = " + ((lo + hi) >>> 1));
        System.out.println("(lo + hi) / 2      = " + (lo + hi) / 2); // int addition wraps around silently
    }
}

// Iterative binary search on the closed range [lo, hi], with a probe counter, then the midpoint of two large bounds.
#include <cstdio>
#include <numeric>
#include <vector>

int probes = 0;

// Index of target in the sorted vector a, or -1; the probes it took are left in `probes`.
int binary_search_index(const std::vector<int>& a, int target) {
    int lo = 0, hi = static_cast<int>(a.size()) - 1;  // invariant: if target is in a, it is in a[lo..hi]
    probes = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        ++probes;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    const std::vector<int> rolls{103, 117, 122, 135, 141, 156, 162, 178, 184, 190, 207, 213, 229, 236, 248, 251};
    for (int target : {141, 200, 300}) {
        int index = binary_search_index(rolls, target);
        std::printf("%d: index %d, %d probes\n", target, index, probes);
    }
    int lo = 1'500'000'000, hi = 2'000'000'000;
    std::printf("lo + (hi - lo) / 2    = %d\n", lo + (hi - lo) / 2);
    std::printf("std::midpoint(lo, hi) = %d\n", std::midpoint(lo, hi));
    std::fflush(stdout);  // so the sanitizer's report, written to stderr, appears next to the line it is about
    std::printf("(lo + hi) / 2         = %d\n", (lo + hi) / 2);  // signed overflow: undefined behaviour
}

// Iterative binary search on the closed range [lo, hi], with a probe counter, then the midpoint of two large bounds.
package main

import "fmt"

// binarySearch returns the index of target in the sorted slice a, or -1, and the number of probes it took.
func binarySearch(a []int, target int) (int, int) {
	lo, hi := 0, len(a)-1 // invariant: if target is in a, it is in a[lo..hi]
	probes := 0
	for lo <= hi {
		mid := lo + (hi-lo)/2
		probes++
		if a[mid] == target {
			return mid, probes
		}
		if a[mid] < target {
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}
	return -1, probes
}

func main() {
	rolls := []int{103, 117, 122, 135, 141, 156, 162, 178, 184, 190, 207, 213, 229, 236, 248, 251}
	for _, target := range []int{141, 200, 300} {
		index, probes := binarySearch(rolls, target)
		fmt.Printf("%d: index %d, %d probes\n", target, index, probes)
	}
	// Go's int is 64 bits wide on 64-bit platforms; int32 shows what a 32-bit index type does.
	var lo, hi int32 = 1_500_000_000, 2_000_000_000
	fmt.Println("lo + (hi-lo)/2 =", lo+(hi-lo)/2)
	fmt.Println("(lo + hi) / 2  =", (lo+hi)/2) // signed integers wrap around
}

from session import run, versions

# BinarySearch.java runs as a single source file, binary_search.cpp is built with the sanitizers on, go run builds Go.
versions("java -version", "clang++ --version", "go version")
run("""
java -XX:-UsePerfData BinarySearch.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined binary_search.cpp -o binary_search && ./binary_search
go run binary_search.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java -XX:-UsePerfData BinarySearch.java
141: index 4, 4 probes
200: index -1, 4 probes
300: index -1, 5 probes
lo + (hi - lo) / 2 = 1750000000
(lo + hi) >>> 1    = 1750000000
(lo + hi) / 2      = -397483648
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined binary_search.cpp -o binary_search && ./binary_search
141: index 4, 4 probes
200: index -1, 4 probes
300: index -1, 5 probes
lo + (hi - lo) / 2    = 1750000000
std::midpoint(lo, hi) = 1750000000
binary_search.cpp:32:53: runtime error: signed integer overflow: 1500000000 + 2000000000 cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior binary_search.cpp:32:53 
(lo + hi) / 2         = -397483648
$ go run binary_search.go
141: index 4, 4 probes
200: index -1, 4 probes
300: index -1, 5 probes
lo + (hi-lo)/2 = 1750000000
(lo + hi) / 2  = -397483648

Every language finds 141 at position 4 and reports 200 and 300 as absent, with the same probe counts. The midpoint lines differ, and the section on overflow below explains why.

Why the loop stops, and how many probes it makes

A loop that never ends is wrong even if it never returns a wrong answer, so the argument needs a quantity that shrinks. Take the size of the range, s = hi - lo + 1. With mid = lo + (s - 1) // 2, a probe that misses leaves either the left part, which has (s - 1) // 2 positions, or the right part, which has s // 2. Either way at most half of s survives, rounded down. A whole number that at least halves on every probe reaches 0, so the loop stops.

The same fact counts the probes. After k probes that all miss, at most ⌊n / 2ᵏ⌋ positions remain, and a probe can only happen while at least one does. So the k-th probe needs 2ᵏ⁻¹ ≤ n, which gives:

Python computes that bound exactly, without floating point, as n.bit_length(). The next program measures the real count for every size from 1 to 2²⁰, searching for a value above all the others, which always takes the larger right part and so makes the most probes. It then tries every present and absent target for every size up to 300:

# Measures the probes of the closed-range binary search for every n from 1 to 2**20 and compares them with
# floor(log2 n) + 1, which Python computes exactly as n.bit_length(). The array is range(n): a[i] == i, sorted, and
# no memory is needed for it.


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


# 1. Every size up to 2**20, searched for a value above all of them. Going right always keeps the larger half
#    (hi - mid >= mid - lo), so this is the longest path the loop can take.
LIMIT = 2**20
mismatches = [n for n in range(1, LIMIT + 1) if probes(range(n), n) != n.bit_length()]
print(f"sizes 1 to {LIMIT:,}: worst-case probes == floor(log2 n) + 1 for all but {len(mismatches)}")

# 2. Every target, present or absent, for every size up to 300: the most any search needs.
worst_all = all(max(probes(range(n), t) for t in range(-1, n + 1)) == n.bit_length() for n in range(1, 301))
print(f"sizes 1 to 300, all {sum(2 * n + 1 for n in range(1, 301)):,} present and absent targets: maximum == floor(log2 n) + 1: {worst_all}")

# 3. A table, and the average of the successful searches.
print()
print(f"{'n':>13}  {'worst probes':>12}  {'floor(log2 n)+1':>15}  {'average when found':>18}")
for n in (1, 2, 3, 7, 8, 100, 1000, 65_536, 1_000_000):
    a = range(n)
    average = sum(probes(a, t) for t in a) / n
    print(f"{n:>13,}  {probes(a, n):>12}  {n.bit_length():>15}  {average:>18.2f}")
n = 10**9
print(f"{n:>13,}  {probes(range(n), n):>12}  {n.bit_length():>15}  {'(not measured)':>18}")

sizes 1 to 1,048,576: worst-case probes == floor(log2 n) + 1 for all but 0
sizes 1 to 300, all 90,600 present and absent targets: maximum == floor(log2 n) + 1: True

            n  worst probes  floor(log2 n)+1  average when found
            1             1                1                1.00
            2             2                2                1.50
            3             2                2                1.67
            7             3                3                2.43
            8             4                4                2.62
          100             7                7                5.80
        1,000            10               10                8.99
       65,536            17               17               15.00
    1,000,000            20               20               18.95
1,000,000,000            30               30      (not measured)

All 1,048,576 sizes meet the bound exactly, and no target of the 90,600 tried needs more. The last column is worth a look: a successful search makes about one probe fewer than the worst case on average, 18.95 against 20 for a million values, because nearly half of the positions are reached only on the last probe, a quarter on the one before, and so on. For a billion values the worst case is 30 probes, a number worth knowing by heart.

Three slips, caught on every small input

Most broken binary searches differ from a correct one by a single token. This program writes the correct search and three common slips, then runs each on every sorted list of up to six values from 0 to 4 against every target from −1 to 5, and stops any search that makes more than 50 probes:

# Three one-token slips in binary search, run on every small case: every sorted list of length 0 to 6 with values
# from 0 to 4, and every target from -1 to 5. A search that makes more than 50 probes is reported as stuck.
from itertools import combinations_with_replacement

LIMIT = 50


class Stuck(Exception):
    pass


def make_search(loop, on_small, on_big):
    """A closed-range binary search with one of its three decisions replaced."""
    def search(a, target):
        lo, hi, probes = 0, len(a) - 1, 0
        while loop(lo, hi):
            probes += 1
            if probes > LIMIT:
                raise Stuck
            mid = lo + (hi - lo) // 2
            if a[mid] == target:
                return mid
            if a[mid] < target:
                lo = on_small(mid)
            else:
                hi = on_big(mid)
        return -1
    return search


VERSIONS = {
    "correct": make_search(lambda lo, hi: lo <= hi, lambda m: m + 1, lambda m: m - 1),
    "while lo < hi": make_search(lambda lo, hi: lo < hi, lambda m: m + 1, lambda m: m - 1),
    "hi = mid": make_search(lambda lo, hi: lo <= hi, lambda m: m + 1, lambda m: m),
    "lo = mid": make_search(lambda lo, hi: lo <= hi, lambda m: m, lambda m: m - 1),
}

cases = [(list(a), t) for n in range(7) for a in combinations_with_replacement(range(5), n) for t in range(-1, 6)]
print(f"{len(cases):,} cases")
for name, search in VERSIONS.items():
    wrong = stuck = 0
    first = None
    for a, t in cases:
        try:
            got = search(a, t)
            ok = (got == -1 and t not in a) or (0 <= got < len(a) and a[got] == t)
            outcome = None if ok else f"returned {got}"
        except Stuck:
            outcome = "stuck"
        if outcome:
            wrong += outcome != "stuck"
            stuck += outcome == "stuck"
            first = first or f"{a} target {t}: {outcome}"
    print(f"{name:14} wrong {wrong:4}  stuck {stuck:4}" + (f"  first: {first}" if first else ""))

3,234 cases
correct        wrong    0  stuck    0
while lo < hi  wrong  342  stuck    0  first: [0] target 0: returned -1
hi = mid       wrong    0  stuck 1181  first: [0] target -1: stuck
lo = mid       wrong    0  stuck 1435  first: [0] target 1: stuck

• while lo < hi stops one probe early: when the range has shrunk to a single position, that position is never read. It returned −1 for 342 targets that were present, the first one being 0 in the list [0].
• hi = mid keeps a position that was already ruled out. On a one-position range whose value is too big, hi stays where it was, the range never shrinks, and the loop is stuck: 1,181 cases.
• lo = mid fails in the mirror image, on the same one-position range when its value is too small: 1,435 stuck cases.

Notice that each slip fails on a list with a single value. Tests on long lists alone can pass every one of them, while 3,234 tiny cases expose all three in a few milliseconds. Exhaustive tests on small inputs, with a limit that turns a hang into a failure, are the cheapest protection a search has.

Midpoints that cannot overflow

The midpoint (lo + hi) // 2 is exact in Python, whose integers have no fixed size. In languages with fixed-width integers, the sum can be too big to store even when lo, hi and the midpoint all fit. With the bounds 1,500,000,000 and 2,000,000,000, the sum is 3,500,000,000, while a 32-bit signed integer stops at 2,147,483,647. The recorded runs above show what each language does with it:

• Java wraps the sum around without any warning: section 4.2.2 of the Java Language Specification guarantees that integer arithmetic raises no error and sets no flag on overflow. The midpoint comes out as −397,483,648, and reading the array there would throw an exception.
• C++ treats signed overflow as undefined behaviour. Built with the undefined-behaviour sanitizer, the program reports the overflow at its exact line before printing whatever value followed. Without it, nothing is reported.
• Go defines signed overflow as wrapping, so int32 gives the same −397,483,648. Go’s int is 64 bits wide on 64-bit systems, which is why slice indices are safe there in practice.
• JavaScript numbers are 64-bit floating-point values, exact for integers up to 2⁵³, so Math.floor((lo + hi) / 2) is right here. The bitwise shortcut (lo + hi) >> 1 first converts the sum to a 32-bit integer and wraps exactly as Java does.

The cure is the form used in every program above: lo + (hi - lo) / 2. The difference hi - lo never exceeds hi, so nothing larger than the bounds themselves is ever computed. C++20 also offers std::midpoint, and Java code often writes (lo + hi) >>> 1, an unsigned shift that reads the wrapped sum correctly. NIST’s Dictionary of Algorithms and Data Structures records the same overflow and the same fix. Array lengths above a billion are rare, but searches over ranges of answers, later in this module, reach these sizes all the time.

When a linear scan is the better choice

Binary search is fast only once the data is sorted, and sorting has a cost. The next program counts comparisons on 10,000 distinct numbers in no particular order: a scan of the unsorted list for one value, a sort of the list, and a binary search in the sorted result.

# Sort once and binary search, or scan the unsorted list every time? Counts the comparisons of each on 10,000
# distinct numbers. Item counts every comparison made on it, by sorted(), list.index() and our own search.
import random


class Item:
    comparisons = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Item.comparisons += 1
        return self.value < other.value

    def __eq__(self, other):
        Item.comparisons += 1
        return self.value == other.value


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


def counted(work):
    Item.comparisons = 0
    work()
    return Item.comparisons


rng = random.Random(7)
values = rng.sample(range(10**6), 10_001)
absent = Item(values.pop())                       # one value that is not in the list
items = [Item(v) for v in values]                 # 10,000 distinct numbers, in no order
keys = rng.sample(items, 200)                     # 200 values that are in the list

scan_found = counted(lambda: [items.index(k) for k in keys]) / len(keys)   # scans of the unsorted list
scan_absent = counted(lambda: absent in items)
sort_cost = counted(lambda: items.sort())                                    # then sort it, once
search_found = counted(lambda: [binary_search(items, k) for k in keys]) / len(keys)
search_absent = counted(lambda: binary_search(items, absent))

print(f"sorting {len(items):,} numbers once: {sort_cost:,} comparisons")
print(f"one key that is there:   scan {scan_found:,.0f}, binary search {search_found:.1f} on average")
print(f"one key that is missing: scan {scan_absent:,}, binary search {search_absent}")
for label, scan, search in (("keys that are there", scan_found, search_found), ("missing keys", scan_absent, search_absent)):
    k = sort_cost / (scan - search)
    print(f"sorting first pays off after about {k:.0f} searches for {label}")

sorting 10,000 numbers once: 120,098 comparisons
one key that is there:   scan 4,943, binary search 23.6 on average
one key that is missing: scan 10,000, binary search 26
sorting first pays off after about 24 searches for keys that are there
sorting first pays off after about 12 searches for missing keys

Sorting cost 120,098 comparisons, and each binary search about 24, against about 4,900 for a scan that finds its value and 10,000 for one that does not. The sort pays for itself after about 24 searches for values that are present, or 12 for values that are missing. Hence a few rules:

• One or a few searches in unsorted data: scan it. Sorting first does more work than it saves.
• Many searches in data that stays the same: sort once, then binary search, or use a hash set when you only need “is it there?”, which the hashing module covers.
• Very short arrays: a scan of a handful of values costs almost nothing and has no boundaries to get wrong.
• Data that changes between searches: keeping an array sorted means shifting values on every insertion, so a balanced search tree or a hash table usually serves better.

Practise: search within a probe budget

Write the search yourself. The starter code is a linear scan that returns the right answers; the tests count how many values your function reads and allow at most ⌊log₂ n⌋ + 1 of them on a list of a million.

def search(nums, target):
    """A position i with nums[i] == target in the sorted sequence nums, or -1."""
    # A linear scan: right, but it reads up to len(nums) values. Replace it with a binary search.
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

from itertools import combinations_with_replacement

from search import search


class Counted:
    """A read-only sorted sequence that counts how many values are read (len() is not counted)."""

    def __init__(self, n, value):
        self.n, self.value, self.reads = n, value, 0

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if isinstance(i, slice):
            raise TypeError("slicing reads many values at once: read one value at a time with nums[i]")
        if i < 0:
            i += self.n
        if not 0 <= i < self.n:
            raise IndexError("index out of range")
        self.reads += 1
        return self.value(i)


def check(values, target):
    got = search(Counted(len(values), values.__getitem__), target)
    if target not in values:
        assert got == -1, f"{target} is not in {values}, so the answer is -1, not {got}"
    else:
        assert isinstance(got, int) and 0 <= got < len(values) and values[got] == target, f"{got} is not a position of {target} in {values}"


def test_small_cases():
    """the empty list, one value, repeats and targets outside the values"""
    for values, target in [([], 3), ([5], 5), ([5], 4), ([2, 2, 2], 2), ([1, 3, 5, 7], 0), ([1, 3, 5, 7], 8), ([1, 3, 5, 7], 4)]:
        check(values, target)


def test_every_small_list():
    """every sorted list of up to 6 values from 0 to 4, with every target from -1 to 5"""
    for n in range(7):
        for values in combinations_with_replacement(range(5), n):
            for target in range(-1, 6):
                check(list(values), target)


def test_reads_on_a_million_values():
    """at most 20 reads on 1,000,000 values (the even numbers 0, 2, ..., 1,999,998)"""
    n = 1_000_000
    for target, expected in [(0, 0), (1_999_998, n - 1), (1_000_000, 500_000), (777_777, -1), (-5, -1), (2_000_001, -1), (123_456, 61_728)]:
        nums = Counted(n, lambda i: 2 * i)
        got = search(nums, target)
        assert got == expected, f"search for {target}: expected {expected}, got {got}"
        assert nums.reads <= n.bit_length(), f"search for {target} read {nums.reads} values; the budget is {n.bit_length()}"

/** A position i with nums[i] === target in the sorted sequence nums, or -1. */
export function search(nums, target) {
  // A linear scan: right, but it reads up to nums.length values. Replace it with a binary search.
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) return i;
  }
  return -1;
}

import { test, assert } from 'mysmartcopilot:test';
import { search } from './search.mjs';

/**
 * A read-only sorted sequence that counts how many values are read (nums.length is not counted) and, like a Python
 * list, refuses positions outside 0 .. n - 1 instead of returning undefined.
 */
function counted(n, value) {
  const state = { reads: 0 };
  const nums = new Proxy(
    {},
    {
      get(_, key) {
        if (key === 'length') return n;
        if (typeof key === 'string' && /^-?\d+$/.test(key)) {
          const i = Number(key);
          if (i < 0 || i >= n) throw new RangeError(`nums[${i}] is outside the ${n} values (positions 0 to ${n - 1})`);
          state.reads++;
          return value(i);
        }
        if (key === Symbol.iterator) {
          return function* () {
            for (let i = 0; i < n; i++) {
              state.reads++;
              yield value(i);
            }
          };
        }
        return undefined;
      },
    },
  );
  return { nums, state };
}

function check(list, target) {
  const { nums } = counted(list.length, (i) => list[i]);
  const got = search(nums, target);
  if (!list.includes(target)) assert.equal(got, -1, `${target} is not in [${list}], so the answer is -1`);
  else assert.ok(Number.isInteger(got) && got >= 0 && got < list.length && list[got] === target, `${got} is not a position of ${target} in [${list}]`);
}

test('the empty list, one value, repeats and targets outside the values', () => {
  for (const [list, target] of [[[], 3], [[5], 5], [[5], 4], [[2, 2, 2], 2], [[1, 3, 5, 7], 0], [[1, 3, 5, 7], 8], [[1, 3, 5, 7], 4]]) {
    check(list, target);
  }
});

test('every sorted list of up to 6 values from 0 to 4, with every target from -1 to 5', () => {
  const lists = [[]];
  for (let n = 1; n <= 6; n++) {
    for (const list of lists.filter((l) => l.length === n - 1)) {
      const last = list.length ? list[list.length - 1] : 0;
      for (let v = last; v <= 4; v++) lists.push([...list, v]);
    }
  }
  for (const list of lists) for (let target = -1; target <= 5; target++) check(list, target);
});

test('at most 20 reads on 1,000,000 values (the even numbers 0, 2, ..., 1,999,998)', () => {
  const n = 1_000_000;
  const budget = Math.floor(Math.log2(n)) + 1;
  for (const [target, expected] of [[0, 0], [1_999_998, n - 1], [1_000_000, 500_000], [777_777, -1], [-5, -1], [2_000_001, -1], [123_456, 61_728]]) {
    const { nums, state } = counted(n, (i) => 2 * i);
    assert.equal(search(nums, target), expected, `search for ${target}`);
    assert.ok(state.reads <= budget, `search for ${target} read ${state.reads} values; the budget is ${budget}`);
  }
});

Interview questions

What does binary search need from its input, and what happens if the array is not sorted?

It needs two things: positions it can reach in one step, as in an array, and values in sorted order, or more generally a yes-or-no test that is false up to some position and true from there on. Without the order, a comparison no longer says which half to throw away, and the search can discard the half that holds the value. It does not crash: it quietly returns a wrong answer. Searching [3, 9, 1, 7] for 1 probes 9 first, decides that 1 must lie to its left, then probes 3, decides the same again, and returns −1 although 1 is at position 2. So check sortedness once when the data arrives, or sort it, rather than trusting it on every search.

Key takeaways

• Binary search keeps one promise: if the target is in the array, it is in a[lo..hi]. Every boundary in the code follows from it: start with 0 and len(a) - 1, loop while lo <= hi, move to mid + 1 or mid - 1.
• The range at least halves on every probe, so the loop stops, after at most ⌊log₂ n⌋ + 1 probes: 20 for a million values and 30 for a billion. Every size up to 2²⁰ was measured to meet the bound exactly.
• The usual slips, while lo < hi, hi = mid and lo = mid, all fail on a one-value list; exhaustive tests on tiny inputs catch them.
• In Java, C++ and Go write lo + (hi - lo) / 2; in JavaScript avoid >> 1 on large sums. Python’s integers cannot overflow.
• For one search in unsorted data, scan. Sorting 10,000 values first paid off only after about 24 searches.