Linear Search

What is linear search?

Let's learn linear search today. And I will explain it so simply that you will understand it right away. Trust me, it is that easy.

So you know those old tape recorders your parents or grandparents used to have? You were probably not even born then and that is okay. A tape recorder was basically your Spotify back in the day. The only thing it could do was play, pause, go forward and go backward. That is it.

Now say there are 100 songs on it and you want to hear a specific one. You cannot just tap it like you do on Spotify. You press play from the very first song. Not your song. Go one forward. Still not it. One more. Still not it. You keep going, one song at a time, until you finally reach the one you wanted.

That is it. That is linear search. You go through everything one by one until you find what you are looking for.

And here is something nice about programming. Most things mean exactly what they sound like in English. Linear means in a straight line, one after another. So linear search simply means searching in a straight line. You will find this a lot as you go further. When in doubt just think about what the word means and you will often be right.

How it works in code

Say our tape has these songs:

string songs[8] = {
    "Blinding Lights", "Levitating", "Stay", "Heat Waves",
    "Peaches", "Watermelon Sugar", "Bad Guy", "Sunflower"
};

We want to find Heat Waves. So we start from the beginning and go one by one until we find it.

First we go through every song, one by one.

for (int i = 0; i < n; i++)

Now at each song we ask, is this the one I am looking for?

if (arr[i] == target)

If yes, we return it. We found it, we are done.

return i;

And if we go through everything and find nothing, we simply return -1. Our way of saying, it is not here.

return -1;

And here is the whole thing together:

int linearSearch(string arr[], int n, string target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

Best case and worst case

Now there are two situations worth knowing about.

The best case is when your song is the very first one. You check once and you are done. One step, no matter how many songs there are.

The worst case is when your song is the last one, or not there at all. You have to go through everything. If there are 1000 songs you check 1000 times. The number of steps grows with the size of the list.

When to use linear search

So when do you actually use linear search?

When your list is small. Say you have 10 contacts in your phone. Just go through them one by one, it will be done before you even think about it. No need to do anything fancy for 10 items.

And when your list is unsorted. If the items are all over the place with no order, linear search does not mind. It just goes through everything anyway.

But say you have a million songs and you are searching through them hundreds of times a day. Going one by one through a million songs every single time is going to be slow. In that case you sort the list once, and then use binary search. Sorting happens one time. But searching happens hundreds of times. So it is worth it.

And that is exactly what binary search is. Instead of going one by one, it cuts the list in half every single step. We will get to that next — Binary search — cut it in half.