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
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.
Linear Search is a possible
Algorithm that can be used in order to solve this problem.
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
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
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.
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.
The Twitter contact:
Any questions? You can get in touch with me here