Halving the Search

Order lets a search throw away half the collection at every step, which turns a million comparisons into twenty. The whole course is about keeping that possible while the data changes.

The last course gave up order to get an instant lookup. This one takes order

seriously, and the first thing order buys is that a single comparison can

eliminate half of everything.

FIG 1Finding 73 among a hundred sorted numbers

step	step	range still possible	middle item	comparison	what is left
1	1	1 to 100	50	73 is larger	51 to 100
2	2	51 to 100	75	73 is smaller	51 to 74
3	3	51 to 74	62	73 is larger	63 to 74
4	4	63 to 74	68	73 is larger	69 to 74
5	5	69 to 74	71	73 is larger	72 to 74
6	6	72 to 74	73	found

6 steps

Six comparisons where a scan would have taken seventy three. What makes this work is that each step removes half of what is left rather than one item, so the range collapses geometrically: a hundred, fifty, twenty four, twelve, six, three. The move is only available because the collection is in order and because the middle item can be reached directly. If finding the middle required walking there, the walk would cost what the search was saving, and that is not a hypothetical, it is exactly what happens to a sorted collection held as a chain of links.

FIG 2The number of halvings

: the number of items in the collection
: the number of halvings until one item is left

Halving k times divides the collection by two to the power of k, and the search ends when that leaves one item, so the number of comparisons is the base two logarithm. The practical readings are worth memorising, since they come up constantly: a thousand items is ten comparisons, a million is twenty, a thousand million is thirty. Every doubling of the data adds exactly one comparison. This is the slowest growth that appears anywhere in computing and it is why, once a collection is in order, searching it is essentially a solved problem.

FIG 3Scanning against halving

scanning, on averagehalving

The straight line is a scan and the flat one is the halving search. At a thousand items the gap is five hundred against ten, and the plot cannot usefully be drawn any wider because the lower curve stops moving: at a million it has reached twenty and at a thousand million thirty. The shape, rather than the particular numbers, is what to take away. One of these methods has a ceiling in practice and the other does not, which is the same distinction the previous course drew between a lookup that grows and one that does not.

FIG 4Searching is cheap, inserting is not

python

import bisect, random, time

n = 1_000_000
items = sorted(random.sample(range(10 * n), n))
wanted = random.sample(items, 1000)

t = time.perf_counter()
for k in wanted:
    bisect.bisect_left(items, k)
print('thousand searches, seconds', round(time.perf_counter() - t, 5))

t = time.perf_counter()
for k in random.sample(range(10 * n), 1000):
    bisect.insort(items, k)
print('thousand insertions, seconds', round(time.perf_counter() - t, 5))

chain = {'value': 1, 'next': None}      # a chain inserts without moving anything
chain['next'] = {'value': 2, 'next': None}
print('can this chain reach its middle directly:', False)

A million sorted numbers. Finding one by halving takes microseconds, and inserting one into the sorted block takes a thousand times longer, because making room means shifting on average half a million items along by one. The structure is excellent at the thing it was built for and almost unusable for anything that changes. The last two lines show why the obvious repair fails: a chain of links inserts without moving anything, and loses the ability to jump to the middle, so the halving search cannot run on it at all.

The tension the course resolves

The halving search needs two things: order, and the ability to jump to the

middle. A block of memory gives both and makes insertion cost half the

collection.

A chain gives cheap insertion and no way to reach the middle. The next lesson

builds the structure that gives both at once, and the four after that are

about keeping it honest.

Recap

A comparison against the middle of a sorted collection eliminates half of it, so the number of comparisons is the number of halvings rather than the number of items.
That is twenty comparisons at a million and thirty at a thousand million, which means the method barely notices the collection growing.
It requires order and the ability to jump straight to the middle, and the second requirement is the one that quietly fails when the collection has to change.

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

NextA Sorted List You Can Change →

Halving the Search

The tension the course resolves

Recap

This is the reading half

Read alongside