An Simplified Explanation of Linear Search

This blog post is a continuation of a series of blog posts about Algorithms, as it has been a hard concept for me to grasp as a programmer. Feel to check out the first blogpost about Algorithms, where I provide an introduction of what Algorithms are and an example of an algorithm and the second blog post about Data Structures, where I explained what are Data Structures and what are some types of Data Structures. Also check out the third blog post about Time Complexity and Space Complexity, which I provide an explanation of Time and Space Complexity. I have also written a blog post about Big O Notation. Recently I have written a blog post about Binary Search.

This blog post I will focus on the Linear Search. I will explain what is the Linear Search, how is Linear Search associated with Algorithms, try to break down the concept of Linear Search step by step and compare to Binary Search. I wanted to spend some more time covering searching algorithms before I move on to sorting algorithms.

What is Linear Search?

A Linear Search is the most basic type of searching algorithm. A Linear Search sequentially moves through your collection (or data structure) looking for a matching value. In other words, it looks down a list, one item at a time, without jumping.

Think of it as a way of finding your way in a phonebook. A Linear Search is starting at the beginning, reading every name until you find what you’re looking for. n complexity terms this is an O(n) search - the time taken to search the list, gets bigger at the same rate as the list does.

Here is an image of Linear Search:

Linear Search: Steps on how it works:

Here is simple approach is to do Linear Search:

• Start from the leftmost element of array and one by one compare the element we are searching for with each element of the array.
• If there is a match between the element we are searching for and an element of the array, return the index.
• If there is no match between the element we are searching for and an element of the array, return -1.

Linear Search: An example

Here is an example of writing the Linear Search algorithm based on the steps I provided earlier. Below I have written a function, which accept the following parameters: values and the target want to find. The function returns the index of the found value.

On a side note I want to provide an explanation of Binary Search before I move on to comparing it with Linear search. A Binary Search is when you start with the middle of a sorted list, and see whether that’s greater than or less than the value you’re looking for, which determines whether the value is in the first or second half of the list. Jump to the half way through the sublist, and compare again etc.

In other words, Binary Search is when you open the phonebook (usually in the middle), look at the name on top of the page, and decide if the name you’re looking for is bigger or smaller than the one you’re looking for. If the name you’re looking for is bigger, then you continue searching the upper part of the book.

Comparison between Binary Search and Linear Search:

• Binary Search requires the input data to be sorted; Linear Search doesn’t
• Binary Search requires an ordering comparison; Linear Search only requires equality comparisons
• Binary Search has complexity O(log n); Linear search has complexity O(n) as discussed earlier
• Binary Search requires random access to the data; Linear Search only requires sequential access (this can be very important — it means a Linear Search can stream data of arbitrary size)

Overall Linear Search is an important concept to understand when it comes to algorithms. Also is important to compare it with other algorithms like Binary Search to see when it is an advantage or disadvantage to use Linear Search. Thank you for reading this blog post. In upcoming blog posts of this series, I will go over sorting algorithms.