Binary search — where it appears
Named by 18 essays across 8 fields — each of them below, with the objects they name alongside it.
A structure made of coin flips
Insert the same 512 keys into a skip list twice, once sorted and once shuffled, from the same seed, and the two structures are identical — the same 11 levels, the same height for every key, the same silhouette. Nothing about the data reached the layout. The 1,064 coin flips did all of it.
The floor moves when the question does
Sorting 4,096 elements needs at least 43,250 comparisons. Finding one element among the same 4,096, already sorted, needs at least 13. The difference is a factor of 3,300 and it comes entirely from how many different answers the algorithm has to be able to give. A lower bound is a property of the question, not of any algorithm.
The tree that is a list
A binary search tree gives logarithmic lookup. Build one from 128 keys in sorted order and it has height 127 — every node has one child, and a lookup is a linear scan. The failure is not gradual and it happens on the input people try first, which makes "O(log n) lookup" a claim about the insertion order rather than about the structure.
When galloping pays
Timsort's merge does not always take elements one at a time. When one run has won seven times in a row it switches to searching for how many to take at once, and switches back when that stops paying. The mode saves 22,104 comparisons on nearly sorted input, 33,270 on input with few distinct values, and costs exactly six on random input — which is the whole design in three numbers.
The priority nobody supplied
Insert 4,096 sorted keys into a binary search tree and it reaches height 4,095, costing 8,386,560 comparisons to build. Give every key a second, random key and keep the tree heap-ordered on that instead, and the same insertion reaches height 26 for 32,750 comparisons. Nothing detected the imbalance, and nothing rebalanced.
A guarantee that depends on an allocation
The C++ standard promises std::stable_sort N log₂ N comparisons if enough extra memory is available, and N (log₂ N)² otherwise. On 65,536 keys the library's own structure, denied its buffer entirely, makes 1,366,510 comparisons — a third more than with it, and twelve times under what the standard allows. What it spends instead is moves: 10.4 million against 1.2 million, 94% of them rotations. The standard bounds the count that barely changes and says nothing about the one that grows as n log² n.
A search with no branch to miss
A binary search does about log₂ n comparisons and every one of them is a coin flip, so it mispredicts once per level. Writing it so the comparison feeds an index instead of a jump costs two thousand extra comparisons over two thousand searches and takes the mispredictions from 17,993 to 2,001 — flat in n, at every size. Under the counters this site had a phase ago, that is a strictly worse algorithm.
Two searches, one comparison count
Three arrangements of the same binary search tree over the same million keys, walking the same path, making the same twenty comparisons. One costs 15 block transfers, one costs 13, and one costs 3. Nothing about the algorithm differs between them — only where the nodes were put — and no counter this site had before this phase could tell them apart.
The cells that were never worth having
Two three-hundred-character strings over twenty-six letters give a table of 90,601 cells, and 3,421 of them are pairs of positions whose characters agree. Only those can lengthen anything. A method that enumerates exactly those computes a twenty-sixth of the table — and on a two-letter alphabet it computes half of it and is worse than the table it replaced.
A tree with nodes the size of a block
A B-tree is a binary search tree that has read the hardware manual. Its node holds as many keys as fit in one transfer, so the height falls from log₂ n to log_B n — and the measured cost falls further still, to 1.01 transfers over four million keys, because the top of the tree is small enough to stay in memory. The comparison count goes up.
The index that is the text
A suffix array sorts all 4,097 suffixes of a text — 8.4 million characters of string, in total — and examines exactly zero characters doing it. It then answers a search in 91 characters where a scan costs 1,472, and the whole thing pays for itself at six queries. Both halves of that are worth the same amount of attention, and the first is the one that is usually skipped.
The floor a merge cannot reach
Merging two sorted lists of five keys each has 252 possible outcomes, so counting says eight comparisons might do. Solving the game says nine are needed, and on equal lengths the shortfall keeps growing, as half the logarithm of the length. Averaged over random inputs, though, the same count is missed by a tenth of a comparison. The counting floor is nearly exact on average and wrong in the worst case.
What it costs to consult two bits a pair
The two-ended selection sort's record of adjacent order can be kept as two bits a neighbouring pair or as a list of runs, and the page that compared them counted both as free to read. Priced, the bits read 1.09 words a question on 1,024 random keys — under the two predicted — and a binary search of the run list takes 8.8 steps, because the pass leaves 503 runs to search. The run list was predicted to win from runs of sixteen keys; it wins only from runs of 512. Both prices are small and neither is small enough. Asked every question the sort makes, the bits spend 201 word reads for every comparison the record saves on runs of four keys, 764 at 4,096 keys, where a table of compared pairs broke even at three. The record repays its reading only on long runs, and the pass that finds them is also the cheapest place to decide whether to consult at all.
A price with no structure under it
A class in this collection has charged Elias–Fano's price for several strands and stores an array of positions searched by binary search. The accounting is right about space to a bit per thousand and wrong about one operation by a factor of eight.
How many pieces the head can afford
A sorted file of 65,536 keys with a late tenth appended in random order can be sorted by taking the tail a buffer at a time, sorting each piece, and merging each into the head. It beats the buffered merge sort at a 64th of the file and loses at smaller buffers, because every piece's merge crosses the head's top keys again. Merging the pieces with each other first, while a round costs less than the crossings it removes, was predicted to win at every buffer. It wins at none. The first round always costs more than no rounds — 18.97 moves a key against 16.04 at a 1,024th — because a group larger than the buffer crosses the head by rotation, and the cost falls under the merge sort's only when the rounds run all the way, which is the merge sort. The head can afford thirteen pieces and not twenty-six; beyond that the best a tail can do is be one run.
The rotation that could be priced
A sort that finds a sorted file with a late tail can send the tail's pieces straight into the head or merge them to one group first, and a rule that priced both ends as shifts chose wrongly at a buffer of a 128th, because a group longer than the buffer crosses the head by rotation. Priced instead from measurements of the library merge on synthetic runs, the long crossing comes within 3% of what the sort pays at every buffer and the choice at a 128th comes right. But the rule prices the pieces against the head as it stood before any of them joined it, and each piece also crosses the pieces before it: priced up to 37% low, they send the sort to the dearer end at a 256th.
The head each piece will meet
A rule that priced a sorted file's late tail two ways before moving anything chose the dearer end at a buffer of a 256th, because it priced every piece against the head as it stood before any piece joined it. Each piece also crosses the pieces before it, and those are known in advance: one binary search of each earlier, already sorted piece counts them. Priced against the head each piece will meet, the pieces come within 6% of what they cost at every buffer, and the rule chooses the cheaper end at all seven buffers and all ten reaches of the tail. A third of what each piece crosses turns out to be other pieces, as the arithmetic of the band says it must.
Every number of rounds, priced
A library merge sort given a file whose last tenth arrived late sorts the tail a buffer's worth at a time and then either sends every sorted piece into the head or merges the pieces first. A rule priced from measured tables chose the cheaper of the two ends at every buffer. Priced the same way at every number of rounds in between, it was predicted never to choose a partway number and to price every one within 6%. It chooses the cheapest number of rounds at all seven buffers on that input and at 14 of 15 settings across reaches and buffers; the one partway optimum among them — six rounds of seven, by 1% — it misses by choosing five, 3.8% dear. But the estimates are not all within 6%. At the three smallest buffers the first round is priced 15% to 25% wrong, high at one buffer and low at the others, because its pairs of pieces cross the head in a way no table of single runs describes; the rule survives it because one round is never close to the cheapest.
Named alongside it
The objects these essays reach for when they reach for this one.
Comparison countMerge sortRotationData movementPredictionAuxiliary spaceBinary search treeStable sortGuaranteeTree heightWorst caseAmortised analysis