Binary Search and Sorting

How does binary search find a value?

Binary search looks at the middle element of a sorted list: if it is the target the search is over; if the target is larger, everything to the left is out; if smaller, everything to the right is out. Repeat on the half that is left. It is the game "I am thinking of a number from 1 to 1000" played well: guess 500, hear "higher", guess 750, and so on. Nobody needs more than 10 guesses.

The algorithm. Keep two indices, lo and hi, with the promise (the invariant) that if the target is in the list, its index is between lo and hi, ends included. Start with lo = 0 and hi = n - 1. While lo <= hi: look at mid, the middle index; if a[mid] equals the target, return mid; if it is smaller, set lo = mid + 1; otherwise set hi = mid - 1. If the interval becomes empty, the target is not there.

Why it is correct. The invariant is true at the start. A look at mid rules out mid itself and one whole side: if a[mid]<x, the list is sorted, so every element at or before mid is smaller than x and the target, if present, lies to the right. So the invariant still holds after each step. The list must be sorted, and it must allow jumping to the middle in one step (an array, not a linked list); otherwise the argument and the speed are both lost.

Why it is fast. An interval of width w becomes one of width at most \lfloor w/2\rfloor. Starting with n, after k looks the width is at most \lfloor n/2^k\rfloor, which is 0 as soon as 2^k>n. So the number of looks is at most \lfloor\log_2n\rfloor+1. That is 10 for 1000 items, 20 for a million, 30 for a billion and 33 for eight billion: each doubling of the list costs one more look. A linear scan of the same list could need n looks (Big-O notation explains the cases).

Type a list and a target below and step through the search. The orange cell is the one being looked at, the faint cells are already ruled out, and the green cell is the answer.

How do you find the first match and avoid off-by-one errors?

Use one template for every question about position: keep a half-open interval of indices lo <= i < hi in which everything before lo is known to be too small and everything from hi on is known to be large enough. With duplicates, "find x" has no single answer, but "the first index with a[i]\ge x" always does. In the list [1,3,3,5,7,7,7,9,12]:

The upper bound minus the lower bound is the number of copies of x: 7-4=3. When x is absent the lower bound is the insertion point, the index where x would go to keep the list sorted, and it may be n (past the end).

The template. Start with lo = 0, hi = n (one past the last index). While lo < hi: take mid = lo + (hi - lo) // 2; if a[mid] < x then lo = mid + 1 (the lower bound is to the right of mid), else hi = mid (mid may be the answer, so keep it). When the loop ends, lo == hi is the answer. For the upper bound, change the test to a[mid] <= x. The invariant is the whole proof: everything before lo is <x, everything from hi on is \ge x, and each step shrinks hi - lo by at least one, so the loop ends.

Where the off-by-one errors come from. Mixing the two conventions: the closed interval lo <= i <= hi goes with hi = n - 1, while lo <= hi and hi = mid - 1; the half-open interval lo <= i < hi goes with hi = n, while lo < hi and hi = mid. Writing hi = mid in a closed interval can loop forever on two elements, and hi = mid - 1 in a half-open one can skip the answer. Choose one and write the invariant as a comment. Jon Bentley found that most professional programmers he tried this on could not write a correct binary search, and Donald Knuth remarked that the first binary search was published in 1946 but a correct one for every length did not appear until 1962.

The overflow bug. The middle is the average of lo and hi, and the obvious formula (lo + hi) / 2 adds them first. In a language with 32-bit integers the sum of two valid indices can be larger than 2 147 483 647 and wrap around to a negative number (see two's complement), as with lo = 1 500 000 000 and hi = 2 000 000 000. In 2006 Joshua Bloch reported that this had been in the binary search of the Java library for years. The safe form is lo + (hi - lo) / 2: the difference is never larger than hi.

How can you binary search for an answer instead of a value?

Binary search needs no list at all, only a yes-or-no question that is false for small numbers and true for large ones: the answer is the place where it switches. The question can be asked about any number, the list never has to exist, and the same loop finds the switch in about \log_2 of the number of candidates.

• An integer square root. The largest r with r^2\le N: the test "m^2\le N" is true for m up to \lfloor√ N\rfloor and false after. For N=123 456 789 the search between 0 and N needs 27 tests to find 11 111 (since 11 111^2=123 454 321 and 11 112^2=123 476 544); counting up from zero would need 11 111. Any N up to 10^12 takes at most 40 tests.
• Finding a bad commit. git bisect asks you whether a version is good or bad; the history goes from good to bad once, so among 1000 commits it finds the first bad one in 10 tests.
• Capacity questions. "What is the smallest truck size that delivers everything in D days?" Bigger always works if smaller does, so binary search on the size, and only write the checking loop.
• A root of a function. If f is continuous and f(a) and f(b) have opposite signs, there is a root between them. Look at the midpoint, and keep the half whose ends still have opposite signs. This is bisection: every step halves the bracket and adds \log_102≈0.30 of a decimal digit, so 50 halvings of [1,2] pin √2 down to 2^-50≈8.9×10^-16, about fifteen digits.

Bisection against Newton's method. Newton's method doubles the number of correct digits at each step, which is far faster, but it needs a derivative and a good starting point and can leave the interval or cycle (see when it fails). Bisection gains only one binary digit per step but cannot fail once the sign changes. Many solvers use both: bisection to be safe, Newton's method to be quick.

Floating-point caution. With real numbers do not loop "until hi - lo < 1e-18": near 1 the doubles are 2.2×10^-16 apart (see the spacing of floats), so hi - lo never gets below that and the loop never ends. Loop a fixed number of times (60 is enough for any bracket of doubles) or stop when mid equals lo or hi.

Try both kinds below: a formula and an interval, or an integer.

How do selection, insertion and bubble sort work?

Selection, insertion and bubble sort are the three simple sorts: each needs about (n^2)/(2) steps, they are short to write, and they are the right choice only for short or nearly sorted lists.

• Selection sort. Find the smallest of the unsorted part and swap it to the front; repeat. It makes exactly (n(n-1))/(2) comparisons whatever the input, but at most n-1 swaps: the one to use if moving an element is very expensive.
• Insertion sort. Take the next number and slide it left past every larger neighbor, as you do with cards in your hand. On a sorted list each number is compared once (n-1 comparisons in all); on a reversed list every number slides all the way.
• Bubble sort. Walk along the list swapping neighbors that are out of order; the largest number is carried to the end on the first pass, the next largest on the second, and so on. With a flag that stops after a pass with no swap, a sorted list costs one pass.

Inversions explain the cost. An inversion is a pair of positions i<j with a[i]>a[j]. The list [5,2,4,6,1,3] has 9: (5,2), (5,4), (5,1), (5,3), (2,1), (4,1), (4,3), (6,1) and (6,3). A sorted list has 0 and a reversed one has (n(n-1))/(2), every pair; a random list has about half of that, (n(n-1))/(4). Swapping two neighbors that are out of order removes exactly one inversion, and so does one shift of insertion sort. So bubble sort makes exactly as many swaps, and insertion sort exactly as many shifts, as the list has inversions, and any method that only moves neighbors needs about (n^2)/(4) steps on a random list. To go faster, a sort must move elements across long distances: that is what merge sort and quicksort do.

Choose an algorithm and an input below and play the bars. Gold bars are being compared, red ones are moving, and green ones are in their final place.

How does merge sort sort in n log n steps?

Merge sort splits the list in half, sorts each half the same way, and then merges the two sorted halves into one. Merging is the easy part: two sorted lists have their smallest elements at the front, so compare the two fronts, move the smaller to the output, and repeat. Merging lists of total length n takes at most n-1 comparisons and exactly n writes.

The recursion halves the list until single elements (already sorted) remain, so there are \lceil\log_2n\rceil levels, and each level merges all n elements once. That is n writes per level and a total of about n\log_2n. The recurrence is T(n)=2T(n/2)+n, solved in the section on recurrences. In exact numbers:

• writes: 8 numbers need 24=8·3, and 1000 need 9976;
• comparisons, worst case: n\lceil\log_2n\rceil-2^\lceil\log_2n\rceil+1, which is 17 for 8 numbers and 8977 for 1000;
• comparisons, already sorted: about half as many, since one list runs out first: 12 for 8 numbers.

Properties. Merge sort needs O(n) extra memory for the merged output, it is stable (if two elements are equal, take the one from the left half first, which is the <= in the code below), and its cost barely depends on the input. It is the natural choice for linked lists and for data on disk or tape, which are read in order; it was the first computer sort, programmed by John von Neumann in 1945.

How does quicksort work, and when is it slow?

Quicksort picks a pivot, moves the smaller elements before it and the others after it, and then sorts the two sides the same way. After the partition the pivot is already in its final place. The partition of Nico Lomuto, used in the code below, takes the last element as the pivot and sweeps from left to right keeping a boundary p: every element smaller than the pivot is swapped to the boundary, which moves one step right. Tony Hoare's original partition uses two pointers moving toward each other and does fewer swaps.

What it costs. A partition of m elements makes m-1 comparisons. If the pivot splits the range roughly in half every time there are about \log_2n levels of about n comparisons each. If the pivot is always the smallest or the largest element, the two sides have sizes 0 and m-1 and the total is (n-1)+(n-2)+…+1=(n(n-1))/(2), quadratic. With the last element as the pivot this happens on an already sorted or reversed list, which is exactly the input people give. On a random list the average is 2(n+1)H_n-4n≈2n\ln n≈1.39 n\log_2n, where H_n=1+\frac12+…+\frac1n. For 1000 elements that is about 10 986 comparisons (against at most 8977 for merge sort), and the chance of a very bad run is tiny.

What real implementations do. - Choose the pivot well: a random element, or the median of the first, middle and last. - Handle equal keys: a three-way partition (smaller, equal, larger) keeps a list of few distinct values from slowing down. - Bound the damage: introsort (David Musser, 1997) switches to heapsort if the recursion gets too deep, so the worst case is O(n\log n); it is behind C++'s std::sort. Recursing into the smaller side first keeps the stack at O(\log n). - Quicksort is not stable, and it sorts in place, with no extra array. Cache-friendly sweeps make it faster than merge sort on arrays in practice, in spite of the extra comparisons.

The sorting race below runs all six algorithms on the same input and counts comparisons and moves.

Which sorting algorithm should you use?

In practice, call the sort of your language: it is a tuned hybrid, and it is almost always faster and more correct than anything you will write. Know what it promises, though.

Three properties decide the choice. Stable: equal keys keep their original order, which lets you sort by several keys in turn (sort by name, then stably by city, and each city is still in name order). In place: only O(1) or O(\log n) extra memory. Adaptive: faster on nearly sorted input, like insertion sort. Heapsort builds a max-heap in the array, then repeatedly swaps the largest to the end and repairs the heap: in place and O(n\log n) in the worst case, but not stable and not cache friendly.

A limit and a way around it. Any sort that only compares elements needs at least \log_2(n!)≈ n\log_2n-1.44n comparisons, because the n! possible orders must be told apart by yes-or-no answers (the idea of the lower bound in the section on cases). For 1000 elements that is 8530 comparisons, and merge sort's worst case, 8977, is within about 5 percent of it. Sorts that do not compare can be faster: counting sort counts how many times each value occurs (O(n+k) for values below k), and radix sort sorts digit by digit with a stable sort, which is how punched-card sorters worked.

What the libraries do. - Python: sorted(a) returns a new list and a.sort() sorts in place and returns None. Both use Timsort (Tim Peters, 2002): it finds runs that are already ordered, extends short runs with insertion sort and merges runs, so it is stable, O(n\log n) and O(n) on sorted input. - JavaScript: array.sort() is stable since 2019, but without a comparator it compares the elements as text, so [10, 9, 1].sort() gives [1, 10, 9]. Always write (a, b) => a - b for numbers. - Java: Timsort for objects, a dual-pivot quicksort for arrays of numbers. C++: std::sort (introsort, not stable) and std::stable_sort.

How do you search and sort in Python, JavaScript and C++?

Write the binary search once with the half-open template and reuse it; in Python the standard library already has it as bisect. The first program below has the lower bound, the closed-interval search that counts its looks, the integer square root by searching the answer, and a comparison with bisect_left and bisect_right. The second program has insertion sort (counting its shifts), merge sort, quicksort (counting its comparisons) and a stable sort by key. The two numbers 9 and 9 in the output are the inversions of [5,2,4,6,1,3] and the shifts of insertion sort: they are equal.

from bisect import bisect_left, bisect_right


def lower_bound(a, x):
    """The first index i with a[i] >= x, in the half-open form [lo, hi)."""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2      # never (lo + hi) // 2 with fixed-size integers
        if a[mid] < x:
            lo = mid + 1               # everything up to mid is too small
        else:
            hi = mid                   # mid itself might be the answer
    return lo


def find(a, x):
    """An index holding x (or -1) and the number of looks, in the closed form [lo, hi]."""
    lo, hi, looks = 0, len(a) - 1, 0
    while lo <= hi:
        looks += 1
        mid = lo + (hi - lo) // 2
        if a[mid] == x:
            return mid, looks
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, looks


def isqrt(n):
    """The largest r with r * r <= n: a binary search on the answer, no list needed."""
    lo, hi = 0, n
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # round up, so that lo = mid always makes progress
        if mid * mid <= n:
            lo = mid
        else:
            hi = mid - 1
    return lo


a = [1, 3, 3, 5, 7, 7, 7, 9, 12]
print(lower_bound(a, 7), bisect_left(a, 7), bisect_right(a, 7))
print(bisect_right(a, 7) - bisect_left(a, 7), lower_bound(a, 4), lower_bound(a, 100))
print(find(a, 5), find(a, 8))
print(isqrt(99), isqrt(100), isqrt(10 ** 12))
big = list(range(0, 2_000_000, 2))     # a million even numbers
print(find(big, 777_776), find(big, 777_777))
# 4 4 7
# 3 3 9
# (3, 4) (-1, 3)
# 9 10 1000000
# (388888, 19) (-1, 20)

def insertion(a):
    """Insertion sort; returns the sorted list and the number of shifts."""
    a, shifts = list(a), 0
    for i in range(1, len(a)):
        x, j = a[i], i - 1
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            shifts += 1
            j -= 1
        a[j + 1] = x
    return a, shifts


def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = (len(a) + 1) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= keeps equal keys in order: the sort is stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]


def quicksort(a, lo=0, hi=None):
    """In place, Lomuto partition, last element as the pivot. Returns the comparisons made."""
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return 0
    p, count = lo, 0
    for j in range(lo, hi):
        count += 1
        if a[j] < a[hi]:
            a[p], a[j] = a[j], a[p]
            p += 1
    a[p], a[hi] = a[hi], a[p]
    return count + quicksort(a, lo, p - 1) + quicksort(a, p + 1, hi)


def inversions(a):
    return sum(a[i] > a[j] for i in range(len(a)) for j in range(i + 1, len(a)))


x = [5, 2, 4, 6, 1, 3]
print(insertion(x), inversions(x))
print(merge_sort(x))
n = 200
print(quicksort(list(range(n))), n * (n - 1) // 2)            # sorted input: the worst case
data = [(i * 73) % n for i in range(n)]                        # a scrambled permutation of 0..199
print(quicksort(data), data == sorted(range(n)))
people = [("Ana", 30), ("Budi", 25), ("Citra", 30), ("Dewi", 25)]
print(sorted(people, key=lambda p: p[1]))                      # stable: Budi stays before Dewi
# ([1, 2, 3, 4, 5, 6], 9) 9
# [1, 2, 3, 4, 5, 6]
# 19900 19900
# 1409 True
# [('Budi', 25), ('Dewi', 25), ('Ana', 30), ('Citra', 30)]

;[10, 9, 1, 100].sort()                      // [1, 10, 100, 9]: no comparator means text order
;[10, 9, 1, 100].sort((a, b) => a - b)       // [1, 9, 10, 100]
const lowerBound = (a, x) => {
  let lo = 0, hi = a.length
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1)        // not (lo + hi) >> 1: see below
    if (a[mid] < x) lo = mid + 1
    else hi = mid
  }
  return lo
}
const a = [1, 3, 3, 5, 7, 7, 7, 9, 12]
;[7, 8, 100].map((x) => lowerBound(a, x))    // [4, 7, 9]
;(1500000000 + 2000000000) >> 1               // -397483648: the sum overflowed 32 bits
1500000000 + ((2000000000 - 1500000000) >> 1) // 1750000000

// bisection: halve a bracket on which f changes sign (60 would be enough for any bracket of doubles)
const f = (x) => x * x - 2
let lo = 1, hi = 2
for (let k = 0; k < 50; k++) {
  const mid = (lo + hi) / 2
  if (f(mid) * f(lo) <= 0) hi = mid
  else lo = mid
}
;[lo, hi, hi - lo]                           // [1.414213562373095, 1.4142135623730958, 8.88e-16]

#include <iostream>
#include <cstdio>
using namespace std;

int lowerBound(int a[], int n, int x) {
  int lo = 0, hi = n;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;                 // not (lo + hi) / 2: it can overflow
    if (a[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

int main() {
  int a[6] = {5, 2, 4, 6, 1, 3};
  int shifts = 0;
  for (int i = 1; i < 6; i++) {
    int x = a[i], j = i - 1;
    while (j >= 0 && a[j] > x) {
      a[j + 1] = a[j];
      shifts++;
      j--;
    }
    a[j + 1] = x;
  }
  for (int i = 0; i < 6; i++) printf("%d ", a[i]);
  printf("\n%d\n", shifts);                        // 9: the number of inversions

  int b[9] = {1, 3, 3, 5, 7, 7, 7, 9, 12};
  printf("%d %d %d\n", lowerBound(b, 9, 7), lowerBound(b, 9, 8), lowerBound(b, 9, 100));
  return 0;
}

/* output:
1 2 3 4 5 6
9
4 7 9
*/

Where do binary search and sorting come from?

Sorting is older than computers, because the machines of the census and the bank needed it, and binary search turned out to be famously easy to get wrong.

• 1890s–1900s. Herman Hollerith's punched-card machines tabulated the 1890 United States census, and the card sorters that followed sorted by one column at a time, the idea of radix sort.
• 1945. John von Neumann wrote merge sort for the EDVAC, the first sorting program for a stored-program computer.
• 1946. John Mauchly described binary search in a lecture series on computing at the Moore School; it is the earliest published description.
• 1959. Donald Shell published Shellsort, the first sort known to beat n^2 by comparing elements far apart. In the same year Tony Hoare invented quicksort, working in Moscow on machine translation; he published it in 1961.
• 1962. By Knuth's account, the first published binary search that is correct for every length of list appeared, sixteen years after the first.
• 1964. J. W. J. Williams published heapsort, and Robert Floyd soon showed how to build the heap in linear time.
• 1997. David Musser designed introsort, the quicksort that cannot degrade.
• 2002. Tim Peters wrote Timsort for Python, and it later spread to Java, Android and JavaScript engines.
• 2006. Joshua Bloch showed that the middle computed as (lo + hi) / 2 in the Java library's binary search and merge sort could overflow for lists of more than 2^30 elements.

What mistakes do people make with searching and sorting?

The most common mistakes with binary search and sorting are the nine below, each with the correct statement.

Practice: test your understanding

These questions mix everything above. A wrong answer costs nothing here: read the hint and try again.

Summary: binary search and sorting at a glance

• Binary search: sorted list, look at the middle, discard half; at most \lfloor\log_2n\rfloor+1 looks.
• Position questions: the half-open template gives the lower bound (first a[i]\ge x); change < to <= for the upper bound; the difference counts copies.
• Bugs: keep one convention with its invariant, and use lo + (hi - lo) / 2.
• Search the answer: any monotone yes-or-no question; integer roots in \log_2N tests; bisection gains one binary digit per step and cannot fail.
• Simple sorts: about (n^2)/(2) steps; bubble and insertion sort move exactly as many times as there are inversions.
• Merge sort: at most n\lceil\log_2n\rceil comparisons, O(n) extra memory, stable. Quicksort: ≈1.39 n\log_2n on average, (n(n-1))/(2) for extreme pivots, in place, not stable.
• Limits: a comparison sort needs \log_2(n!)≈ n\log_2n-1.44n comparisons; counting and radix sort avoid comparing.
• In practice: use the library sort (Timsort, introsort), a stable one for several keys, and a comparator for numbers in JavaScript.

Glossary: key terms

Binary search

A search in a sorted list that looks at the middle element and discards the half that cannot contain the target.

Invariant

A statement that is true before and after every step of a loop, from which the correctness of the loop is proved.

Lower bound (position)

The first index whose element is at least x; for an absent x it is the insertion point that keeps the list sorted.

Bisection method

A way to find a root of a continuous function by repeatedly halving an interval on whose ends the function has opposite signs.

Inversion

A pair of positions in a list where the earlier element is larger than the later one; a sorted list has none.

Stable sort

A sort that keeps elements with equal keys in the order they had before sorting.

In-place sort

A sort that rearranges the list using only a small amount of extra memory.

Pivot

The element quicksort chooses so that smaller elements are moved before it and the others after it.

Comparison sort

A sort that learns the order only by comparing two elements at a time, and so needs about n log n comparisons.

Timsort

The stable hybrid of merge sort and insertion sort used by Python and by Java for objects, fast on data that is partly ordered.

Frequently asked questions

References

1. Donald E. Knuth (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.), sections 5 and 6.2.1. Addison-Wesley.
2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2022). Introduction to Algorithms (4th ed.), chapters 2, 6, 7 and 8: Getting Started; Heapsort; Quicksort; Sorting in Linear Time. MIT Press.
3. C. A. R. Hoare (1961). Algorithm 64: Quicksort. Communications of the ACM 4(7).
4. Joshua Bloch (2006). Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Google Research Blog.
5. Jon Bentley (1999). Programming Pearls (2nd ed.), column 4: Writing Correct Programs. Addison-Wesley.

Related articles

• Big-O Notation: Big-O notation explained: the definition, growth rates from O(1) to O(n!), counting steps in code, best and worst case, recurrences and the Master theorem.
• Newton’s Method: Newton’s method for solving f(x) = 0: the formula from tangent lines, examples, quadratic convergence, when it fails, square roots by hand, and code.
• Floating-Point Numbers: How floating-point numbers work: the IEEE 754 bits, spacing and rounding, NaN and infinity, accumulated errors, cancellation, comparisons, and which type to use.
• Binary Numbers: How Computers Count, Convert and Calculate: Binary numbers explained: bits and place value, converting to decimal and hex, binary arithmetic, two’s complement, bitwise operators and binary fractions.