Searching

You search all the time: a name in your chat history, a song in your playlist, a word in the dictionary. Computers search constantly too, just in much bigger lists. Let's look at how they do it cleverly.

Linear search: one by one

The simplest idea: you go through the list from front to back and check every entry until you find the right one. That's called linear search. It always works, even if the list is a mess. But it can take a while: if the entry you want is at the very end of a list with 1000 entries, you need 1000 steps.

Binary search: always halve

If the list is sorted, it gets much faster. Think of a phone book: you're looking for 'Meier' and open it in the middle. If you see 'Schulz' there, you know right away that 'Meier' is in the front half. You can throw away the back half completely. Then you halve the front half again, and so on. That's binary search: every step cuts the list in half.

Counting steps

A step here always means: you look at one entry and compare it with the one you want. The difference between the two methods is huge. With 1000 entries, linear search needs up to 1000 steps in the worst case. Binary search halves: 1000, 500, 250, 125 and so on. After about 10 halvings only one entry is left. 10 steps instead of 1000! The bigger the list, the more clearly halving wins.

The requirement: sorted

Binary search has a catch: it only works if the list is sorted. Only then does the look at the middle tell you which half to keep searching in. In an unsorted list, linear search is your only option. That's why sorting is so important, and that's exactly what the next topic is about.