Linear Search

If this isn’t the one you are looking for, try the next

This is a rather basic searching algorithm, but it is actually useful in practice when you just need to find an element in an array — and you suspect the element is towards the beginning of the array (or just don’t want to think too hard)

Difficulty: Beginner | Easy | Normal | Challenging

Prerequisites:

• Know what an algorithm is (unsure? Guide HERE)
• Be able to read Pseudocode
• Know what an array is (Guide HERE)

Terminology

Iteration: Each time a set of instructions is executed in a loop is an iteration

Linear Search: An algorithm to look for a target within an array, starting with the first item and moving through the next one in turn until the element is found

Why do we need to search

To find an item on a computer, we need to think like a computer. Each time a computer checks to see if the item is the one it wants, that is a comparison.

And here is the thing: Comparisons cost time.

Now computers are inherently ordered things. This might be surprising, but essentially what I’m saying is that computers aren’t completely disorganised.

If you have a large collection of numbers (and let us use numbers as examples of searching) you would put them together in an array to find a specific entry.

Imagine you want to store the age of a set of people to do some clever mathematical modelling. Perhaps there is some reason that you want to ensure that there is someone who is exactly 40 years old.

A `Linear Search` is a possible `Algorithm` that can be used in order to solve this problem.

The example

So imagine we have 5 numbers stored in an array, in the order that they originally were created in.

These 5 numbers are 15, 2, 104, 112 and 3 in this case. We will try to find 104 in the `Array`.

As you can see we have placed the numbers into the array. We will then traverse the `Array` to try to find out whether 104 is present.

There is something going on here though. At step 3 of the `Algorithm` above we have found our element, yet we have continued for two more `Iterations` of the `Algorithm`.

This is quite wasteful — if we think about this we can actually just stop when we’ve found the element we are looking for.

So we can explain this `Linear Search Algorithm` with a flowchart, with the slight efficiency improvement to stop when the item is found already added.

This is also represented by the following pseudocode

Why Linear Search Isn’t Great

Linear search compares each and every element in turn. This means that you potentially need to check each and every element in your list before you find the target! Because there are n elements in the list, potentially you have to make n comparisons to find the target.

We say in the worst case there are n comparisons, so the algorithm is O(n).

Here we are measuring the efficiency of the algorithm by looking at the worst case. The worst case is that the item we are looking for is right at the end of the array.

You should know that the worst case scenario happens more often than you think.

Conclusion:

When we look for an item in an array or other data structure we do rather need to think of the efficiency of our `Algorithm`. If you wanted to watch a particular movie on Netflix (say Mortdecai or entourage) you would not want the algorithm to look through every possible film on the service before telling you if it is there or not.

A divide a conquer algorithm like Binary Search (Explained in the Swift programming language HERE) can be a much better choice for such a use.

You can argue, though, that in some cases (like a small `array`) going through a simple algorithm like `Linear Search` makes sense.

As with much in programming, it is up to the programmer to decide. The best course of action is that which you choose, so it is best to at least attempt to choose wisely.

Happy coding…