Linear Search in Python – A Practical Approach

Let us learn about a simple and straightforward searching algorithm in Python.

The Linear Search Algorithm

Linear Search works very similar to how we search through a random list of items given to us.

Let us say we need to find a word on a given page, we will start at the top and look through each word one by one until we find the word that we are looking for.

Similar to this, Linear Search starts with the first item, and then checks each item in the list until either the item is found or the list is exhausted.

Let us take an example:

Theoretical Example of the Linear Search Algorithm

Consider,

• List: 19, 2000, 8, 2, 99, 24, 17, 15, 88, 40
• Target: 99

So, we need to find 99 in the given list. We start with the first item and then go through each item in the list.

• Item 1: 19, not found.
• Item 2: 2000, not found.
• Item 3: 8, not found.
• Item 4: 2, not found.
• Item 5, 99, target found, end loop.

So, we have found the given target after five checks at position 5.

If the given target was not in the list, then we would have gone through the entire list and not found the item, and after the end of the list, we would have declared the item as not found.

Note that we are looking at each item in the list in a linear manner, which is why the algorithm is named so.

A Note on Efficiency

Linear Search is not a very effective algorithm, it looks through each item in the list, so the algorithm is directly affected by the number of items in the list.

In other terms, the algorithm has a time complexity of O(n). This means that if the number of items in the list is multiplied by an amount, then the time it takes to complete the algorithm will be multiplied by that same amount.

There are better search algorithms out there like Sentinel, Binary, or Fibonacci Search, but Linear Search is the easiest and the most fundamental of all of these which means that every programmer should know how to use it.

Implementing Linear Search Algorithm in Python

def linear_search(lst, target):
    for i in range(len(lst)):
        if(lst[i] == target):
            return i
    return -1

Let us look at the code,

• We are creating a function for linear search that takes in two arguments. The first argument is the list that contains the items and the second argument is the target item that is to be found.
• Then, we are creating a loop with the counter i, i will hold all the indexes of the given list, i.e., i will go from 0 to length of the list – 1.
• In every iteration, we are comparing the target to the list item at the index i.
• If they are the same, then that means that we have found the target in the list at that index, so we simply return that index and end the loop as well as the function.
• If the entire list is checked and no items are returned, then the control will move out of the list, and now we are sure that the target item is not in the list, so we return -1 as a way of telling that the item was not found.

Let us look at how the algorithm will behave for an item in the list and another item that is not in the list:

The Output

Here, we send two items as the target: 99, which is in the list at index 4, and 12, which is not in the list.

As we can see, the algorithm returned the index 4 for 99, and -1 for 12. which indicates that 99 is at index 4, and 12 is absent from the list, and hence the algorithm is working.

Conclusion

In this tutorial, we studied a very easy and simple searching algorithm called the Linear Search.

We discussed how Linear Search works, we talked about its efficiency and why it is named “linear”.

Then we looked at how the algorithm is written in Python, what it does, and confirmed that by looking at the output of the code.
I hope you learned something, and see you in another tutorial.