Data Structures and Algorithms: Linear Search

The Linear Search Algorithm

As the name says a linear search is a process that starts at the beginning of a list and goes through every element (one item at a time) until it finds the element which is looking for. To find the element which is searching for (for example we are searching for x), a linear search algorithm is comparing every element in the list with the value inside of x, until a match is found or the whole list has been searched. Performance for using linear search in large lists is bad because it makes at most n comparisons, where n is the length of the list. In practice, linear search algorithm is rarely being used because other search algorithms like the binary search algorithm allow significantly faster searching for all but shortlists.

Implementing Linear Search Algorithm

A linear search algorithm is usually simple to implement and is practical when the list is short with only a few elements, or when we are performing a single search in an unordered list. If we want to write a linear search algorithm obvious choice will be to use a for loop. To search the list we will be using a range expression to get all index values from 0 to the length of the list minus one. We will be testing every index in the body of the loop to see if it contains the item which we are searching for. Let's see an example of a linear search algorithm in Python using a for-loop.

def linearSearch(a, x):
  for i in range (0, len(a)):
    if a[i] == x:
      return i
  return None

Linear search imlementation in Python using for loop

At the beginning of the example we are defining a function linearSearch with two arguments (a and x) where a is the list and the x is the element we are searching for. Inside the function, we have for-loop which iterate through every item from the start at 0 to the end at the size of the list. Inside the for-loop we are testing every index(a[i]) with the value of x, if the test is true we are returning the index where we wound the element. If the for-loop ends and no matching element is found in the list, the function will return None at the end.

We can also use a while-loop instead of for-loop for the linear search algorithm, using the for-loop the code look cleaner but at the end is the matter of writing style.

Analysis of Linear Search Algorithm

For a given list with n size of items, the best case is when the value is equal to the first element of the list, in which case only one comparison is needed. The worst case is when the value is not in the list or occurs only once at the end of the list, in which case n comparisons are needed.

If you want to learn more in-depth about algorithms and data structures, I highly recommend you to check this book: Introduction to Algorithms, 3rd Edition (The MIT Press)