Linear Search

Introduction

Linear search is the simplest search algorithm. The goal of Linear Search is to find an element in an array by looking comparing it with every element in the array. Linear search is a brute force algorithm.

Visualization

Given a problem to find the position of number one in an array of 4 elements [4, 7, 1, 2].

With linear search, we have to check each element. So we start with the element at position 0 (4)

This element doesn't match what we aim to find, so we move to the next.

The next iteration is also a failure, so we move to the next

The third iteration gives us our desired result, so we return the index.

Python implementation

def linearSearch(arr, item):
    for i in arr:
        if (i == item):
            return True
    return False

The code block above shows the python implementation of linear search. The function linearSearch takes two parameters, arr which is the array to be searched and item which is the item to be found.

Asymptotic analysis

Linear search = O(n)

Since every item of the list is considered, it means increasing the number of items will simply increase the time taken to complete the search. This means linear search is bound by O(n) for both time and space complexity.

Real-world application

Linear search is rarely used in the real world. It can be seen as a demonstration algorithm. If it were to be used, it will be used to search through small datasets (~ <50 items).