Linear Search

In this tutorial, we'll learn about Linear Search, the simplest Search Algorithm there is out there.

What is a Linear Search?

A Linear Search is the simplest and easiest Search Algorithm out there. It loops over an array (a list), and checks every item for the target element. Of course, it isn't very efficient if your element is at the end of the list and you have a lot of elements in your list. So, a Linear Search isn't often used in programming, but it is a fundamental idea.

Linear Search Implementation

Due to its simplicity, a Linear Search is very easy to implement. We only need to iterate, or loop, over a list of elements and check if any of them are the same as the element we are looking for. Below is the implementation of a Linear Search:


def linear_search(arr, x):
    """Finds the index of x in arr using a Linear Search Algorithm"""
    for index in range(len(arr)):
        if arr[index] == x:
            return index
    return -1

Running the Code

The code is written in a simple function. It performs a Linear Search on the array, arr, and finds the first occurence of the value of x. If the element is not found, the program returns -1. Otherwise, it returns the index where x is found.

Code Breakdown

The code for a Linear Search is very simple. On the first line, we define a function with

def linear_search(arr, x):

On the next line, we have a multi-line string. When you put a multi-line string on the line right after declaring a function, we call it a doc-string, which tells the developer a little bit about the function. Then, we have our main code:


for index in range(len(arr)):
    if arr[index] == x:
        return index

In the code, we loop (or iterate) over the arry/list. For each item, we check if the element is equal to our target. If it is, then we'll return the index where we find it. When we return something in Python, we automatically break out of the function, so our function will return the first occurence of the target, if it finds it.

Finally, on the last line, we have return -1. This will just return -1 if the target is not found.