Finding what you want fast
When you look up a word in a dictionary, you don't flip from the first page. You open the middle and decide "front or back." If it's in order, you can cut in half each time and find it much faster.
One by one, from the start
The simplest way to search
is to look from the start, one by one.
"This one? No.
Next? No."
You keep flipping
until it matches.
It's sure, but
if it's near the back,
it takes a while.
One by one from the front. (Target 13 · check one box at a time)
With only a few boxes,
it's fine.
But what about thousands?
Going one by one
takes ages.
There's a better way.
A clever way you use
when things are in order.
Open the middle
When it's in order,
do this.
Open the middle and look.
If your target is bigger,
throw away the front half.
If smaller, the back half.
Each time you look,
half disappears.
Look at the middle, throw away half. (Target 13 · drop the half it isn't in)
Throwing away half each time,
what's left shrinks fast.
8 boxes to 4,
4 to 2,
2 to 1.
In just a few steps
it narrows to one box.
One by one vs by half
Put the two side by side
and search the same value.
One by one
has to look many times
for a value near the back.
By half
finishes in a few.
Same answer,
but the step counts differ a lot.
Find the same value (13), compare steps. (One by one = slow · by half = fast)
The more boxes,
the bigger the gap.
A thousand one by one
is up to a thousand looks,
by half about ten.
This gap, with big data,
is enormous.
Why sorting comes first
Cutting in half
has one condition.
It must be in order.
Only when sorted
does "if it's bigger than the middle, drop the front"
hold true.
If jumbled,
you can't throw away a half.
Cutting in half works only when sorted. (In order → works · jumbled → doesn't)
So sorting and searching
are partners.
Line it up once,
and from then on searching
keeps getting faster.
The effort of tidying
pays off again and again.
Look how far we've come
Searching is always nearby.
A dictionary, a phone book,
one word typed in a search box.
Behind it,
a way like "cut in half"
finds the answer fast.
Order, sorting, searching
now connect in one line.
Order → sorting → searching, this far. (Search = picking out what you want, fast)
An algorithm
is nothing grand,
you can see that now.
Setting an order,
tidying up,
searching cleverly.
Small tricks gathered
do big things.