Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture VIII of XIV

Lecture VIII · Data Structures & Algorithms

Binary search and the quadratic sorts

A sorted list is a promise, and the whole of this lecture is about what that promise buys you. Lecture III taught us to read growth off the shape of a loop, and it named O(log⁡n)O(\log n) as the reward for halving the problem at every step. Binary search is where that reward gets collected. But it only works if the list holds up its end of the bargain, so we start with the contract.

The ordered list, and the contract it offers

Before any code, walk into Babbidge and find a book. You have a call number, say QA76.9, and there are two million volumes in the building. Nobody has ever suggested you find it by starting at the front door and reading spines. You go to the floor for Q, walk to the QA range, and then, standing in front of a shelf, you do the thing this entire lecture is about: you glance at a spine roughly in the middle of the run, read QA402, decide “too early,” and walk right, ignoring everything to the left forever. Three or four glances and you have it.

Notice what made that possible, because it was not the size of the library and it was not your cleverness. It was a promise, made by the library and kept by the staff, that the volumes are in call-number order. That promise is what turns one glance into information about a thousand books you did not look at. Take the promise away and the whole method evaporates: on a shelf in no particular order, reading QA402 in the middle tells you exactly nothing about what is to its left or its right, and there is no honest alternative to walking the whole run. This is why a misfiled book is, from the searcher’s point of view, a lost book. It is sitting right there in the building, and the procedure everyone uses to find things will walk straight past it.

An ordered list is just a list that agrees to stay sorted. That sounds like a small thing. It is not. Once a list is sorted, one value tells you about all the others: if you look at the middle element and it is too big, every element to its right is also too big, and you can dismiss half the list without touching it. An unsorted list gives you no such leverage. To know whether a value is present you have to look at every cell, because any cell you skip might be the one holding it. That is the linear scan, O(n)O(n), and there is no way around it when the data is in no particular order.

So the ordered list ADT is a bargain. You promise to keep the data sorted, and in return you get to search it in O(log⁡n)O(\log n) instead of O(n)O(n). Like every ADT, it is defined by its operations and their guarantees, not by how they are implemented: a contains query that runs in logarithmic time, an insert that puts a new value in its rightful place, and the standing invariant that at all times the elements are in nondecreasing order. Everything that follows is the fine print on that bargain: how the fast search actually works, why it is so easy to get wrong, and what the promise to stay sorted costs you when you insert.

Binary search, done right

Here is the idea in one breath. Keep a window of the list where the target could still be, look at the middle of that window, and use what you see to throw away half. Repeat until you either land on the target or run out of window. The window starts as the whole list, a[lo..hi] with lo at 0 and hi at the last index, and it shrinks every step.

The engine that makes this correct is a single sentence you can hold in your head, the loop invariant: if the target is anywhere in the list, it is somewhere in a[lo..hi]. That sentence is true before the loop starts, because at the start the window is the whole list. And every step is designed to keep it true. You look at mid, the middle of the current window. If a[mid] equals the target, you are done. If a[mid] is smaller than the target, then because the list is sorted, everything from lo through mid is also too small, so the target, if present, must be to the right: you set lo = mid + 1 and the invariant still holds. If a[mid] is larger, the mirror image happens and you set hi = mid - 1. Either way the window got strictly smaller and the invariant survived. When lo passes hi the window is empty, and the invariant now says the target was never there.

The plate below makes the window visible. Watch the live window stay lit while the eliminated cells grey out, and watch the probe counter climb slowly, one per halving. Then flip to Manual mode and pick your own probe. The plate will tell you whether your choice keeps the invariant, and whether it actually halves the window or just wastes a step.

the target 45, if present, lies in a[0..14] · window = 15 · probes = 0 · ⌈log₂ n⌉ = 4

lo 3 0
8 1
12 2
19 3
23 4
27 5
34 6
mid 41 7
45 8
52 9
58 10
63 11
70 12
77 13
hi 88 14

Sorted sample of 15. The midpoint a[7] = 41 is the first cell to test; each probe halves the live window.

Plate I THE INVARIANT WATCHER · Binary search on a sorted array, with the loop invariant printed at every step: the target, if present, lies in a[lo..hi]. The live window stays lit; eliminated cells grey out. Press Step or Play for the textbook search, then switch to Manual and probe a cell yourself: a probe outside the window is flagged illegal, and an off-centre probe is flagged correct-but-slow.

The probe counter is the payoff. Every probe throws away half of what remained, so the number of probes is the number of times you can halve n before nothing is left, which is about ⌈log⁡2n⌉\lceil \log_2 n \rceil. That is why binary search is O(log⁡n)O(\log n), and log⁡n\log n is a stunningly small number. A thousand elements take about ten probes. A million take about twenty. Double the list and you pay exactly one more probe. This is the same log⁡n\log n class Lecture III put on the log-log plot, and here is where it earns its keep.

The trick is that you are counting halvings, not elements. Halving 1000 down to 1 takes about ten steps, because 2 to the tenth is 1024. A million is 2 to the twentieth, so about twenty probes. A billion is 2 to the thirtieth, so about thirty. The list grew by a factor of a million between the first and last question, and the work grew from ten to thirty. That flatness is the whole reason we keep lists sorted.

The invariant is the correctness proof

Binary search is famous for being easy to describe and brutal to get exactly right. The canonical study found that most published versions had bugs, and they were almost never in the idea. They were in the boundaries: lo < hi versus lo <= hi, mid versus mid + 1, whether the window is allowed to be empty. These are the off-by-one errors, and they all live in the same neighbourhood, the edge of the window.

The invariant is what lets you settle every one of them without guessing. Ask, at each line, does this keep the target inside a[lo..hi]? Take the loop condition. Should it be while lo <= hi or while lo < hi? The window a[lo..hi] contains exactly one element when lo == hi, and that element might be the target, so you must still test it: the condition is lo <= hi. Take the update. After testing mid and finding it too small, may you write lo = mid? No: you already know a[mid] is not the target, so leaving it in the window would let the loop test it again forever. You have proven mid is not the answer, so you exclude it with lo = mid + 1. Every boundary decision has a right answer, and the invariant hands it to you.

This is the same discipline Lecture II built around contracts and tests, seen from the inside of a loop. A contract says what a function guarantees to its caller; an invariant says what a loop guarantees to itself on every pass. Both turn “I think this is right” into “here is why this cannot be wrong.” Trace the search below with the window printed at each probe, and confirm the invariant holds line by line. The Trace button lets you scrub lo, hi, and mid as they move.

python runs in your browser · first run downloads ~240 kb
Plate II TRACING THE WINDOW · A correct binary search that prints its window a[lo..hi] at every probe, searching once for a present value and once for an absent one. Press Run to read the windows, or Trace to step through lo, hi, and mid as names.

Two honest baselines: insertion and selection sort

Binary search needs sorted input, so sooner or later you have to sort. Before the clever O(nlog⁡n)O(n \log n) methods (a later lecture), it is worth writing the two simplest sorts by hand, because they are honest baselines: correct, obvious, and just fast enough to be useful on small inputs. Both are O(n2)O(n^2), and seeing exactly why is the point.

Selection sort does what its name says. Walk the list; at each position, select the smallest element from everything that remains and put it there. To find that smallest you scan the rest of the list, which is a loop; you do that for every position, which is a loop around the loop. Nested loops over the same data are the canonical quadratic, so selection sort does about n2/2n^2/2 comparisons no matter what the input looks like.

def selection_sort(a):
    for i in range(len(a)):
        m = i
        for j in range(i + 1, len(a)):   # find the smallest of what remains
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]          # swap it into position i
    return a

Insertion sort works the way you sort a hand of cards. Keep the front of the list sorted, take the next element, and slide it left past everything larger until it drops into its place. The sliding is an inner loop, and it runs inside the outer walk, so in the worst case (a list sorted backwards, where every element slides all the way to the front) it is again about n2/2n^2/2.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:     # slide larger elements right
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key                   # drop key into the gap
    return a

The plate races these against each other and against merge sort, counting comparisons on the same array. On a couple dozen elements the quadratic trio already does several times the work of merge sort, and the gap only widens with n. Shuffle a few times and watch the counts.

Comparison and move counts for four sorting algorithms on a fixed 12-element sample, showing merge sort using far fewer comparisons than the quadratic three.
algorithm order compares moves
Bubble n^2 66 58
Insertion n^2 38 40
Selection n^2 66 22
Merge n log n 32 44

Sample of 12 values; shuffle a live array to watch the race.

Operation counts for every algorithm on the current array.
algorithm order compares moves
Plate III THE SORTING RACE · Insertion, selection, and bubble sort (all O(n2)O(n^2)) against merge sort (O(nlog⁡n)O(n \log n)) on one shuffled array. Compared bars carry each method's own hue, the settled region green; the scoreboard counts comparisons and moves for every method at once. Even on two dozen elements the quadratic trio does several times merge's work. Toggle Invariant to band the region each quadratic sort has already locked in: insertion and selection settle a growing left prefix (a[0..i]), bubble a growing right suffix (a[n-i..]), one more cell per pass over the unsorted rest, which is the n(n−1)/2n(n-1)/2 triangular sum behind O(n2)O(n^2) (merge merges runs, so it shows no single band). Press Speedrun for a fresh array and a scored attempt: every comparison you spend is charged to you, including the ones you spend on a method you abandon, so the cheapest run is the one where you read the array before you choose.

When O(n2)O(n^2) is the right answer

It would be a mistake to file the quadratic sorts under “slow, never use.” Insertion sort in particular is the method the good library sorts fall back to, and for two concrete reasons that big-O deliberately hides.

The first is small n. Insertion sort has tiny constants: its inner step is a comparison and a shift, nothing more, with no recursion, no extra array, no bookkeeping. For a handful of elements that low overhead beats the setup cost of a cleverer method, which is exactly why real-world sorts switch to insertion sort once a sub-problem gets small. Lecture III warned that big-O hides constants; this is that warning cashed out in production code.

The second reason is the shape of the input. Insertion sort is adaptive: on a list that is already sorted, every element is already bigger than the one before it, so the inner slide never runs and the whole thing is a single pass, O(n)O(n). On a nearly-sorted list, where only a few elements are out of place, it is close to that. Selection sort has no such gift, because it scans the whole remaining list to pick a minimum whether or not the data is already in order: it is O(n2)O(n^2) on sorted, reversed, and random input alike. So insertion sort is the right tool exactly when n is small or the data is nearly sorted, and those two cases happen constantly. An honest baseline is not a bad algorithm. It is the one you reach for when the input is friendly.

Stability, and the sort you can trust twice

There is a second property that separates these two sorts, and unlike speed it does not show up in any big-O at all. A sort is stable if records that tie on the sort key come out in the order they went in. If Ana and Bo both live on the second floor, and Ana was ahead of Bo in the input, then a stable sort by floor keeps Ana ahead of Bo. An unstable sort makes no such promise and may hand them back either way.

You can read stability straight off the inner loop, which is the part worth learning. Insertion sort slides an element left while a[j] > key, strictly greater, so it stops the instant it meets an equal element and the new record settles behind the tied one already in place. Change that one comparison to >= and insertion sort becomes unstable, which is a good measure of how delicate the property is. Selection sort has no such luck. It works by swapping a far-away minimum into position, and that long-range swap picks up whatever element was sitting in the destination and flings it to the other end of the array, right past its equals. Selection sort is unstable, and no rearrangement of the comparisons fixes it, because the instability is in the swap and not in the test.

python runs in your browser · first run downloads ~240 kb
Plate IV STABLE AND UNSTABLE, SIDE BY SIDE · Five records sorted by floor with insertion sort and with selection sort. Press Run: insertion returns Ana before Bo, as they arrived, while selection's long-range swap flings one past the other. The second half is the payoff, sorting by name first and then stably by floor, so both orders hold at once.

Why should you care about a property that costs nothing and changes no running time? Because stability is what lets you sort by two keys without writing a two-key comparison. Sort your records by name, then sort that result stably by floor, and you get floors in order with names alphabetical inside each floor, for free, because the stable second pass never disturbed the work of the first. Every spreadsheet’s “sort by this column, then that one” is this trick. It is also why Python’s built-in sort guarantees stability in the language specification rather than leaving it to the implementation: too much real code quietly depends on it.

Insertion sort’s genuine win, measured

We claimed insertion sort is adaptive and selection sort is not. That is the sort of claim that deserves a number rather than a nod, so let us count comparisons on four shapes of the same sixty-four values: already sorted, nearly sorted (four adjacent pairs swapped), shuffled, and reversed.

Predict the table before you run it. Selection sort’s inner loop runs from i + 1 to the end no matter what it finds, because it cannot know it has the minimum until it has seen everything, so its count should be exactly n(n−1)/2n(n-1)/2 on all four rows. Insertion sort’s inner loop has a break in it: the moment it meets an element that is not larger than the key, it stops, because everything further left is smaller still. On sorted input that break fires immediately every single time, so it does one comparison per element, n−1n - 1 in total, and that is O(n)O(n).

python runs in your browser · first run downloads ~240 kb
Plate V THE ADAPTIVITY TABLE · Comparison counts for insertion and selection sort on the same 64 values arranged four ways. Press Run: selection's column is constant at 2016 across all four rows, while insertion runs from 63 on sorted input to 2016 on reversed. The nearly-sorted row is the one that matters in practice.

Read the nearly-sorted row, because it is the one that describes real data. Log files arrive almost in timestamp order. A leaderboard changes by a few positions between refreshes. A list you sorted yesterday and appended six items to is sorted except at the end. In every one of those cases insertion sort’s count barely moves off the sorted-input floor, while selection sort pays full quadratic price for information it already had. This is also exactly why the industrial sorts behave the way they do: Python’s Timsort begins by hunting for runs that are already in order and extending them with a binary insertion sort, on the theory that real data is rarely a fresh shuffle. Insertion sort is not the algorithm you scale with. It is the algorithm the good ones are made out of.

Back to the shelf: what a misfiling costs

Now take that binary search back into the stacks, because the library makes vivid a failure mode that an array of integers hides. Our search assumes the shelf is in order. What happens, concretely, if it is not?

Not an error. Not a crash. Not a slow answer. You get a confident, fast, wrong one. The search reads a spine, concludes on the strength of the sortedness promise that the volume it wants must be to the right, and abandons half the run, including the shelf the volume is actually sitting on. It reports “not on this shelf” in three probes, and it is wrong, and nothing in the algorithm has any way to notice. That is the price of an unchecked precondition: it does not fail loudly, it fails plausibly.

python runs in your browser · first run downloads ~240 kb
Plate VI THE MISFILED VOLUME · A short run of call numbers searched in order, then searched again after one volume is refiled at the wrong end. Press Run and compare the last two lines: the volume is on the shelf at index 0, and binary search reports -1 without hesitation, in three probes, having ruled out the very shelf it was standing on.

Two lessons come out of that, and the second is the general one. First, the sortedness promise is a precondition of the algorithm, in exactly the sense Lecture II gave that word, and preconditions are the caller’s job. Verifying it inside the search would cost O(n)O(n) and so destroy the very thing you came for; the honest design is to state the requirement and put the burden on whoever owns the list. Second, and more broadly, this is what makes fast algorithms dangerous. Linear scan is slow and unkillable: hand it a shuffled shelf and it still finds the book. Binary search is fast because it trusts, and everything it trusts is something you must guarantee elsewhere. Speed in this business is nearly always bought with an assumption, and part of the craft is knowing which assumption you just signed for.

Half-open windows, and where the off-by-ones live

We said the invariant settles the boundary questions, and it does. But there is a second discipline, one you can adopt once and stop making a whole family of mistakes, and it is worth stating outright: be consistent about which end of the window is included.

There are two coherent conventions. The closed window a[lo..hi] includes both ends, which is what we have written so far. Its invariant reads: if the target is present it lies in a[lo..hi]; the window is empty exactly when lo > hi; the loop runs while lo <= hi; and a ruled-out mid is excluded by moving past it, lo = mid + 1 or hi = mid - 1. The half-open window a[lo..hi) includes the left end and excludes the right. Its invariant reads: if the target is present it lies in a[lo..hi); the window is empty exactly when lo == hi; the loop runs while lo < hi; and the right update is plain hi = mid, because mid is already outside a window whose right end is exclusive.

Both are correct. Neither is more correct. Almost every off-by-one in binary search is a programmer who has half of one convention and half of the other: the <= from the closed form with the hi = mid from the half-open form, say, which loops forever on the last element. The half-open form is the one worth defaulting to, for three reasons that are not about taste. The length of the window is just hi - lo, with no stray plus one. The empty window is lo == hi, and there is no -1 in the initialisation to special-case an empty list. And it is the convention Python already uses everywhere: range(0, n), a[i:j], and the bisect module all mean “from here, up to but not including there.”

python runs in your browser · first run downloads ~240 kb
Plate VII THREE WINDOWS · The closed and half-open searches side by side, each reporting its index and its probe count, plus the classic broken version whose window is allowed to stop shrinking. Press Run: the first two return the same index on every query (their probe counts differ by one here and there, which is all the two conventions ever disagree about), and the broken one runs to its 40-step safety cap looking for a value that is not there. Remove the cap in a real program and it never returns.

The broken function in that bench is worth one more look, because it is the most common binary-search bug and the invariant explains it in one sentence. Writing lo = mid instead of lo = mid + 1 keeps a cell in the window that you have already proven is not the target. The invariant survives (the target really is still in a[lo..hi]) but a second obligation quietly dies: the window no longer strictly shrinks. Correctness needs both. An invariant tells you the answer is still in there; a variant, some quantity that provably decreases every pass, is what tells you the loop ever stops. Here the variant is the window’s width, and lo = mid is the line that stops it going down.

bisect_left, bisect_right, and the ADT for real

One more thing the textbook binary search does badly. Ours returns -1 when the target is absent, which is a fine answer to “is it there?” and a useless answer to almost every other question. Where would it go if I inserted it? How many copies are there? What is the smallest element greater than this one? The -1 throws away everything the search learned on the way down.

So the version worth actually knowing does not report presence at all. It reports an insertion point: the index where the value belongs, whether or not it is already there. Run the loop until the window is empty and return lo, and you get exactly that. With duplicates in the list there are two defensible insertion points, before the run of equals and after it, and they differ by one character in the comparison:

  • bisect_left(a, x) uses a[mid] < x, strictly less, so a tie pushes hi down and you land at the first position where x could go, which is the index of its first occurrence when it is present.
  • bisect_right(a, x) uses a[mid] <= x, so a tie pushes lo up and you land after the last occurrence.
python runs in your browser · first run downloads ~240 kb
Plate VIII LEFT AND RIGHT · Both variants run against a sorted list with duplicates, tabulating the left index, the right index, their difference, and presence. Press Run: for x = 3 the pair is 1 and 4, so there are three copies starting at index 1; for the absent x = 4 the two agree at 4, and a difference of zero is exactly what absence means.

Look at what that pair of numbers gives you. bisect_right(a, x) - bisect_left(a, x) is the number of copies of x, counted in O(log⁡n)O(\log n) without touching them. Non-zero means present, so containment is a special case rather than a separate function. bisect_left is the index to insert at to keep the list sorted while putting the newcomer ahead of its equals; bisect_right puts it behind them, which for records with a tie-break is the stable choice and the same idea as stability in the sorts. And “the first element greater than x” is just a[bisect_right(a, x)], if that index is in range.

That is the ordered-list ADT as it actually gets used, and it is why Python ships bisect in the standard library rather than a plain binary_search. The general lesson is bigger than this one function: when you design an operation, ask whether the natural answer is richer than the yes-or-no you were about to return. A search that reports where is strictly more useful than a search that reports whether, and it costs not one extra probe.

Keeping sorted versus sorting once

That leaves the real design question the ordered list ADT poses: do you keep the list sorted as you go, or sort it once when you need it? The bargain has a cost on the other side of the ledger. Binary search finds where a new value belongs in O(log⁡n)O(\log n), but putting it there means shifting every larger element one slot to the right to open a gap, and that shift is O(n)O(n). Inserting into a sorted array is O(n)O(n) no matter how fast you found the spot, because an array stores its elements in contiguous slots and making room means moving them.

So the choice comes down to how your workload is mixed. If you search far more often than you insert, keep the list sorted: each insert costs O(n)O(n), but every one of the many searches is a cheap O(log⁡n)O(\log n), and you come out ahead. If instead you insert a whole batch and only then search, do not pay the O(n)O(n) insert over and over; dump everything in unsorted, sort once for O(nlog⁡n)O(n \log n), and search the result. And if inserts and searches are interleaved and both must be fast, the array is the wrong structure entirely: keeping a sorted sequence with a fast insert is precisely the problem that motivates the balanced search trees a later lecture builds. For now, hold the tradeoff clearly: sorted input is what makes binary search possible, and staying sorted is not free. Knowing which side of that bargain your program lives on is half of choosing the right structure.

Exercises

  1. You run binary search on a sorted list of 64 elements for a value that turns out to be absent. Exactly how many probes does it make in the worst case before it reports “not found,” and why is the absent case not slower than the present case? Give the number and one sentence of reasoning.

  2. Here is a tempting but broken loop condition: while lo < hi. Describe a tiny input on which it returns the wrong answer, and name the invariant it violates. (Hint: think about the moment the window has shrunk to a single cell.)

  3. Selection sort does the same number of comparisons on an already-sorted list as on a shuffled one, but insertion sort does far fewer on the sorted list. Explain the difference in terms of each algorithm’s inner loop, and say which of the two you would choose to keep a mostly-sorted log file in order as new lines trickle in.

  4. The speedrun, played properly. Press Speedrun on Plate III and, before touching anything else, look at the bars. Then choose one method and sort it. Play three attempts and write down the comparison count each time. Now answer two questions. First: which method wins on a freshly shuffled array of 24, and roughly by what factor? Second: the run charges you for comparisons spent on a method you abandon halfway, so what is the cost of “just trying Bubble to see”? Say in one sentence what the scoreboard is really asking you to practise, given that in real code you choose the algorithm once and never watch it run.

  5. Half-open by hand. Rewrite the loop condition and the two updates of the search you know in the half-open convention: hi starts at len(a), the loop runs while lo < hi, and the right update is hi = mid. Then answer: on a list of one element, how many probes does each convention make before it reports an absent value, and where exactly would each one loop forever if you wrote lo = mid instead of lo = mid + 1?

  6. Implement binary_search(a, x): given a sorted list a, return the index of x, or -1 if it is absent. It must run in O(log⁡n)O(\log n), which means halving the window each probe, not scanning. The checks cover the places where off-by-one bugs hide: an empty list, a one-element list present and absent, the target at the very front and very back, absent values below, above, and between the elements, and a longer list where every present key must land at its own index. Protect the invariant and the boundaries will take care of themselves.

    The checks · run against your code

    # empty list returns -1
    assert binary_search([], 5) == -1
    # single element, present
    assert binary_search([7], 7) == 0
    # single element, absent
    assert binary_search([7], 3) == -1
    # target at the front
    assert binary_search([2, 4, 6, 8, 10], 2) == 0
    # target at the back
    assert binary_search([2, 4, 6, 8, 10], 10) == 4
    # target in the middle
    assert binary_search([2, 4, 6, 8, 10], 6) == 2
    # absent, between two values
    assert binary_search([2, 4, 6, 8, 10], 5) == -1
    # absent, below the whole range
    assert binary_search([2, 4, 6, 8, 10], 1) == -1
    # absent, above the whole range
    assert binary_search([2, 4, 6, 8, 10], 99) == -1
    # every present key lands at its own index in a longer list
    assert all(binary_search(list(range(0, 200, 2)), 2 * k) == k for k in range(100))
    python runs in your browser · first run downloads ~240 kb
    Plate IX IMPLEMENT BINARY SEARCH · Fill in the loop so the window a[lo..hi] halves toward x. Run to grade against ten checks built around the empty list, the single element, both ends, and absent values below, between, and above the data.
    Hint one

    The window is a[lo..hi] with lo starting at 0 and hi at len(a) - 1. Loop while lo <= hi, because a window with lo == hi still holds one untested element.

    Hint two

    Each pass, compute mid = (lo + hi) // 2 and compare a[mid] to x. On a match, return mid. If a[mid] < x, the answer is to the right, so lo = mid + 1; otherwise hi = mid - 1. Use mid + 1 and mid - 1, never plain mid, so the window always shrinks.

    The solution

    The window shrinks by at least one every pass and never re-tests a cell it has already ruled out, so the loop terminates, and the invariant guarantees a correct answer:

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

    The empty-list case works for free: hi starts at -1, so lo <= hi is false immediately and the function returns -1 without a single probe. Every loop runs about ⌈log⁡2n⌉\lceil \log_2 n \rceil times, so this is O(log⁡n)O(\log n), the reward the sorted list was holding out the whole time.

  7. The version worth knowing. Implement bisect_left(a, x): the first index at which x could be inserted into the sorted list a with the list staying sorted. It must never scan. Use the half-open window, and note the one structural difference from the search above: there is no early return on a match, because a match is not the end of the story when duplicates are allowed. The loop runs until the window is empty and then returns lo.

    The checks · run against your code

    # the insertion point in an empty list is 0
    assert bisect_left([], 5) == 0
    # below everything
    assert bisect_left([2, 4, 6], 1) == 0
    # above everything
    assert bisect_left([2, 4, 6], 9) == 3
    # a present value lands at its FIRST occurrence
    assert bisect_left([1, 3, 3, 3, 5], 3) == 1
    # an absent value lands where it would be inserted
    assert bisect_left([1, 3, 3, 3, 5], 4) == 4
    # a list that is all one value
    assert bisect_left([7, 7, 7, 7], 7) == 0
    # inserting at the returned index keeps the list sorted
    a = [1, 3, 3, 5]
    a.insert(bisect_left(a, 4), 4)
    assert a == [1, 3, 3, 4, 5]
    # it must be exact on a long list too
    big = list(range(0, 2000, 2))
    assert bisect_left(big, 1000) == 500
    assert bisect_left(big, 1001) == 501
    python runs in your browser · first run downloads ~240 kb
    Plate X BISECT LEFT, GRADED · Halve a half-open window [lo, hi) until it is empty, then return lo. Run to grade against nine checks: the empty list, values below and above the whole range, a run of duplicates, a list that is entirely one value, and a long list where the answer must be exact.
    Hint one

    Set lo, hi = 0, len(a) and loop while lo < hi. Note there is no - 1 anywhere in the setup, which is the half-open convention paying for itself: the empty list gives lo == hi == 0 immediately and the loop never runs, so 0 falls out for free.

    Hint two

    Inside, take mid = (lo + hi) // 2 and ask one question only: a[mid] < x. If yes, everything up to and including mid is too small, so lo = mid + 1. Otherwise hi = mid, keeping mid as a candidate right end because it might itself be the first position x belongs at. Do not return early on equality; equality belongs in the else branch, and that is exactly what makes this bisect left.

    The solution

    Five lines, no special cases, and the invariant is now about the answer rather than about the target: every position before lo holds something strictly less than x, and every position from hi on holds something not less than x.

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

    When the loop ends, lo == hi, so those two facts meet and pin the answer exactly. Change the one comparison to a[mid] <= x and you have bisect_right, which lands after the run of equals instead of before it. Two functions, one character apart, and between them they answer contains, count, insertion point, and next-larger, all in O(log⁡n)O(\log n).

  8. Both ends of a run. Implement search_range(a, x), returning the pair (first, last) of indices bounding every occurrence of x in the sorted list a, or (-1, -1) if it is absent. The tempting solution is to find any occurrence and then walk outward, and it is wrong on cost: a list of a million identical values would make that walk O(n)O(n) and undo everything. Two halving searches, no walking.

    The checks · run against your code

    # an empty list has nothing
    assert search_range([], 3) == (-1, -1)
    # an absent value between two present ones
    assert search_range([1, 2, 4], 3) == (-1, -1)
    # a single element, present
    assert search_range([5], 5) == (0, 0)
    # a run of three in the middle
    assert search_range([1, 3, 3, 3, 5], 3) == (1, 3)
    # a list that is entirely the target
    assert search_range([2, 2, 2, 2], 2) == (0, 3)
    # a run that touches the front
    assert search_range([1, 1, 3, 5], 1) == (0, 1)
    # a run that touches the back
    assert search_range([1, 3, 5, 5], 5) == (2, 3)
    # the count falls straight out of the pair
    first, last = search_range([1, 3, 3, 3, 5], 3)
    assert last - first + 1 == 3
    python runs in your browser · first run downloads ~240 kb
    Plate XI THE RUN, BOUNDED · Two nearly identical binary searches, differing in one comparison, bracket a run of equal values. Run to grade against eight checks, including a list that is entirely the target and runs that touch either end.
    Hint one

    Write two helpers first, the pair from Plate VIII: one that lands at the first position x could occupy and one that lands just past the last. Then the whole function is arithmetic on their two answers.

    Hint two

    Let L be the left insertion point and R the right one. If R == L there are no occurrences at all, so return (-1, -1). Otherwise the first occurrence is at L and the last is at R - 1, because R is one past the end of the run. Notice you never have to check whether x is present as a separate step; the two indices already say so.

    The solution

    The absence test is a subtraction, which is the neatest thing about this pair of functions:

    def search_range(a, x):
      lo, hi = 0, len(a)
      while lo < hi:                  # bisect_left, inlined
          mid = (lo + hi) // 2
          if a[mid] < x:
              lo = mid + 1
          else:
              hi = mid
      left = lo
    
      lo, hi = 0, len(a)
      while lo < hi:                  # bisect_right: the only change is <=
          mid = (lo + hi) // 2
          if a[mid] <= x:
              lo = mid + 1
          else:
              hi = mid
      right = lo
    
      if right == left:
          return (-1, -1)
      return (left, right - 1)

    Two logarithmic searches is still O(log⁡n)O(\log n), since 2log⁡n2\log n and log⁡n\log n are the same growth class. On [2, 2, 2, 2] the walk-outward version would touch every element and be O(n)O(n); this one makes four probes. That is the difference between “found it” and “found where it starts and where it ends,” and it is entirely in refusing to scan even once you have a hit.

  9. The main event, part two. Write sort_by_second(pairs): sort a list of (name, key) pairs by the key alone, using insertion sort, keeping it stable, and returning a new list without disturbing the input. Two of the checks exist purely to catch instability, and one exists to catch you sorting in place. Get the inner comparison exactly right and all of it falls out.

    The checks · run against your code

    # the empty list and the single pair
    assert sort_by_second([]) == []
    assert sort_by_second([("a", 1)]) == [("a", 1)]
    # it sorts by the key, ignoring the name
    assert sort_by_second([("a", 3), ("b", 1), ("c", 2)]) == [("b", 1), ("c", 2), ("a", 3)]
    # ties keep their original order: this is stability
    assert sort_by_second([("a", 2), ("b", 2), ("c", 1)]) == [("c", 1), ("a", 2), ("b", 2)]
    # a longer stability check with three tied keys
    p = [("Ana", 2), ("Bo", 2), ("Cy", 1), ("Di", 3), ("Ed", 2)]
    assert sort_by_second(p) == [("Cy", 1), ("Ana", 2), ("Bo", 2), ("Ed", 2), ("Di", 3)]
    # the input list is not modified
    assert p[0] == ("Ana", 2)
    assert len(p) == 5
    # an already-sorted input comes back unchanged
    q = [("a", 1), ("b", 2), ("c", 3)]
    assert sort_by_second(q) == q
    python runs in your browser · first run downloads ~240 kb
    Plate XII STABLE INSERTION SORT, GRADED · Sort pairs by their second element while preserving the arrival order of ties. Run to grade against seven checks, including a three-way tie, an untouched input, and an already-sorted list that must come back unchanged.
    Hint one

    Copy first: a = pairs[:]. A slice of the whole list is a new list, so the caller’s list is safe, and the pairs inside are tuples and cannot be mutated anyway. Then run the insertion sort you already know over a.

    Hint two

    The only change from the plain version is what you compare. The elements are pairs, so compare a[j][1] against key[1], never the whole pair (that would tie-break on the name and destroy stability). And keep the comparison strictly greater: while j >= 0 and a[j][1] > key[1]. Sliding past an equal key is exactly the bug the stability checks are hunting for.

    The solution

    Textbook insertion sort with two small edits, a copy at the top and an index into the pair in the comparison:

    def sort_by_second(pairs):
      a = pairs[:]
      for i in range(1, len(a)):
          key = a[i]
          j = i - 1
          while j >= 0 and a[j][1] > key[1]:   # strictly greater keeps ties put
              a[j + 1] = a[j]
              j -= 1
          a[j + 1] = key
      return a

    Change that one > to >= and the third and fourth checks go red while everything else stays green, which is a fair picture of how stability bugs behave in the wild: the output is still sorted, so nothing looks broken, and the only symptom is that somebody’s two-pass sort quietly stops working. Run it on an already-sorted input and note the other half of the lecture showing up as well: the inner loop never executes, so the whole call is a single pass.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.