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 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, , 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 instead of . 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
Sorted sample of 15. The midpoint a[7] = 41 is the first cell to test; each probe halves the live window.
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 . That is why binary search is , and 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 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.
Two honest baselines: insertion and selection sort
Binary search needs sorted input, so sooner or later you have to sort. Before the clever 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 , 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 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 .
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.
| 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.
| algorithm | order | compares | moves |
|---|
When 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, . 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 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.
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 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, in
total, and that is .
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.
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 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.”
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)usesa[mid] < x, strictly less, so a tie pusheshidown and you land at the first position wherexcould go, which is the index of its first occurrence when it is present.bisect_right(a, x)usesa[mid] <= x, so a tie pushesloup and you land after the last occurrence.
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 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 , but putting it there means shifting every larger element one slot to the right to open a gap, and that shift is . Inserting into a sorted array is 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 , but every one of the many searches is a cheap , and you come out ahead. If instead you insert a whole batch and only then search, do not pay the insert over and over; dump everything in unsorted, sort once for , 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
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.
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.)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.
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.
Half-open by hand. Rewrite the loop condition and the two updates of the search you know in the half-open convention:
histarts atlen(a), the loop runswhile lo < hi, and the right update ishi = 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 wrotelo = midinstead oflo = mid + 1?Implement
binary_search(a, x): given a sorted lista, return the index ofx, or-1if it is absent. It must run in , 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 kbPlate 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]withlostarting at 0 andhiatlen(a) - 1. Loopwhile lo <= hi, because a window withlo == histill holds one untested element.Hint two
Each pass, compute
mid = (lo + hi) // 2and comparea[mid]tox. On a match, returnmid. Ifa[mid] < x, the answer is to the right, solo = mid + 1; otherwisehi = mid - 1. Usemid + 1andmid - 1, never plainmid, 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 -1The empty-list case works for free:
histarts at-1, solo <= hiis false immediately and the function returns-1without a single probe. Every loop runs about times, so this is , the reward the sorted list was holding out the whole time.The version worth knowing. Implement
bisect_left(a, x): the first index at whichxcould be inserted into the sorted listawith 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 returnslo.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 kbPlate 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 loopwhile lo < hi. Note there is no- 1anywhere in the setup, which is the half-open convention paying for itself: the empty list giveslo == hi == 0immediately and the loop never runs, so 0 falls out for free.Hint two
Inside, take
mid = (lo + hi) // 2and ask one question only:a[mid] < x. If yes, everything up to and includingmidis too small, solo = mid + 1. Otherwisehi = mid, keepingmidas a candidate right end because it might itself be the first positionxbelongs 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
loholds something strictly less thanx, and every position fromhion holds something not less thanx.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 loWhen the loop ends,
lo == hi, so those two facts meet and pin the answer exactly. Change the one comparison toa[mid] <= xand you havebisect_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 .Both ends of a run. Implement
search_range(a, x), returning the pair(first, last)of indices bounding every occurrence ofxin the sorted lista, 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 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 kbPlate 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
xcould occupy and one that lands just past the last. Then the whole function is arithmetic on their two answers.Hint two
Let
Lbe the left insertion point andRthe right one. IfR == Lthere are no occurrences at all, so return(-1, -1). Otherwise the first occurrence is atLand the last is atR - 1, becauseRis one past the end of the run. Notice you never have to check whetherxis 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 , since and are the same growth class. On
[2, 2, 2, 2]the walk-outward version would touch every element and be ; 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.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) == qpython runs in your browser · first run downloads ~240 kbPlate 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 overa.Hint two
The only change from the plain version is what you compare. The elements are pairs, so compare
a[j][1]againstkey[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 aChange 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.