What is the Linear Search Algorithm

Last week, we described binary search in Python. In this tutorial, we’re going to do the same thing with a new search algorithm: the linear search algorithm.

The linear search algorithm is one of the simplest search algorithms. The input to a linear search algorithm is an array or list and an item. The algorithm searches for the presence of the item inside the array. If the item is found, the index of the item is returned. Otherwise, it can return null or any other value that you think can’t exist inside the array.

Here are the basic steps for performing a the linear search algorithm in Python:

  1. Search the input item at the first index (0 index) of the array.
  2. Check if the item is found at the current index. If yes, return the index and move to step 5.
  3. Check if the current index is the last index of the array. If yes, return null and move to step 5.
  4. Move to the next index in the array and go to step 2.
  5. Stop the algorithm.

Dry Run the Linear Search algorithm

Before we implement the linear search algorithm in Python, let’s try to step through the logic of the linear search algorithm using an example.

Suppose we have a list of integers and we want to search for the integer 15 inside the list. Your Python setup might look something like this:

nums = [4,9,15,21,25,28,35,38,40,45]

item = 15

Iteration 1

Step 1: Search the item 15 at the 0th index of the nums array.

Step 2: Check if 15 exists at the current index (index 0). This will not return true since the current index contains the item 4. So we move to step 3.

Step 3: Check if the current index is the last index of the nums array. Since this also returns false, we move to the next step.

Step 4: Move to index 1 of the nums array and go to next iteration, which starts from the second step.

Iteration 2

Step 2: Check if 15 exists at the current index (index 1). This will not return true since the current index contains the item 9. So we move to step 3.

Step 3: Check if the current index is the last index of the nums array. Since this returns false, we move to the next step.

Step 4: Move to index 2 of the nums array and go to next iteration, which starts from the second step.

Iteration 3

Step 2: Check if 15 exists at the current index (index 2). This will return true since the current index contains the item 15. The index 2 will be returned to the calling function and we move to step 5.

Step 5: Stop the algorithm.


Get Our Python Developer Kit for Free

I put together a Python Developer Kit with over 100 pre-built Python scripts covering data structures, Pandas, NumPy, Seaborn, machine learning, file processing, web scraping and a whole lot more - and I want you to have it for free. Enter your email address below and I'll send a copy your way.

Yes, I'll take a free Python Developer Kit

Implementation of the Linear Search Algorithm in Python

Since the logic of the linear search algorithm is really simple, the implementation of the linear search algorithm in Python is likewise simple. We create a for loop that iterates through the input array. If the item is found at any index of the array, that array index is printed and we can break the for loop. Otherwise, if the for loop ends and the item is not found, we can print that the item is not found.

Here is a non-function implementation of the linear search algorithm in Python.

nums = [4,9,15,21,25,28,35,38,40,45]

item = 38


value_found = False

for i in range(len(nums)):

    if nums[i] == item:
        value_found = True
        print("Item found at index ", i)
        break

if value_found == False:
    print("Item not found")

Output:

Item found at index  7

And here is a function implementation of the linear search algorithm. The function lin_search() in the following script accepts an input array and the item to be searched as its parameters.

Inside the function a for loop iterates through all the items of the input array. If the item is found at any index, the index value is returned. Otherwise, the Null value is returned.

def lin_search(nums, item):

    for i in range(len(nums)):

        if nums[i] == item:
            value_found = True
            return i

    return None


nums = [4,9,15,21,25,28,35,38,40,45]

item = 40

index = lin_search(nums, item)
if index != None:
    print("Item found at index", index)
else:
    print("Item not found")

Output:

Item found at index 8

The time complexity of the linear search algorithm is N where N is the number of items in the input array. This is the case where the item is found at the last index of the input array after iterating through all the array items.

Clearly, the linear search algorithm isn’t the most efficient way to find an element’s position in a list, but learning how to program the logic of a linear search still remains a useful skill in Python or any other programming language. If you found this helpful and want a few more Python programming examples, enter your email address below.