How does search work in algorithms
When you look up a word in a dictionary, you don't turn the pages one by one from the start. You open it in the middle and decide whether the word is before or after. If things are in order, you can find what you want much faster by cutting in half like this.
One at a time from the start
The simplest way to search is to look at each item from the start.
"Is this it? No. The next one? No." You keep going until you find it.
It's certain, but if the value is near the end, it takes a long time.
Press "search one by one" to check one cell at a time from the front. The target is 13.
With only a few cells, that's fine.
But with thousands or tens of thousands, checking one at a time takes forever.
There's a better way, a clever one you can use when things are in order.
Open to the middle
When things are in order, you do this: first, open to the middle and look.
If the value you want is bigger, throw away the front half; if it's smaller, throw away the back half.
Each look gets rid of half.
Each press of "check middle" throws away the whole half that can't contain the target. The target is 13.
Throwing away half each time shrinks what's left fast.
8 cells become 4, 4 become 2, and 2 become 1.
In just a few looks, you're down to a single cell.
One at a time vs half at a time
Put the two side by side and search for the same value.
Searching one at a time has to look many times to reach a value near the end, while halving finishes in a few looks.
Same answer, very different number of steps.
Searching for the same value (13), compare the steps. One at a time = slow · halving = fast.
The more cells there are, the wider the gap.
With a thousand items, one at a time can take up to a thousand looks, while halving takes about ten.
With big data, that difference is enormous.
Why sorting comes first
Halving has one condition: things have to be in order.
Only when they're sorted does "if it's bigger than the middle, you can throw away the front" hold true.
If things are jumbled, you can't throw away half.
Halving only works when things are sorted. In order → it works · jumbled → it doesn't.
That's why sorting and searching go together.
Once you've lined things up, searching stays fast from then on.
The effort you put into tidying pays off again and again.
How far we've come
Searching is always around us.
Dictionaries, phone books, the word you type into a search box: behind them, methods like halving find the answer fast.
Order, sorting, and searching are now joined in one line.
Order → sorting → searching: this is how far we've come. Searching = quickly picking out what you want.
By now you can see that algorithms aren't anything grand.
Setting an order, tidying up, and searching cleverly.
Small tricks add up to big results.