Linear Search Explained with Example

In this post we're going to explore the Linear Search algorithm and walk through step-by-step coding of a Linear Search example in Python. By the end of this post, you should have a solid understanding of how Linear Search works and how to implement it in Python. This post is a part of the algorithm series where we plan to cover different algorithms gradually.

See the Video on Linear Search in YouTube

What is Linear Search?

Linear Search is a basic searching algorithm that checks every element in a list or array one by one until the target element is found or until the entire list is searched. For example we can consider a list of 5 numbers

7, 15, 24, 27, 0

The indexes will be 0, 1, 2, 3 and 4. Let's say we want to find the number 27 from the list.

How Linear Search Works

Linear Search starts from the beginning of the list and compares each element with the target element until it either finds a match or reaches the end of the list.

So it will start from the beginning, index 0, which has 7, it will compare 7 with our target number 27. 7 doesn't match with 27 so it will move to the next index, index 1 where it will search for 27. But index 1 has 15, so it will move to index 2 containing 24 which also not a match. So it will move on to the index 3 where 27 is found.

Algorithm Logic

Let's define the algorithm with some steps:

1. Start from the first element of the list.
2. Compare the current element with the target element.
3. If it matches, return the index.
4. If not, move to the next element.
5. Repeat steps 2-4 until the end of the list is reached.
6. If the target element is not found, return -1 to indicate it's not in the list.

Implementing Linear Search

Now, let's write code to implement a Linear Search example in Python.

First, we need to import any necessary libraries. Lets import random library to generate random number for our list.

# Import libraries
import random

Next, let's create a list to search through. We are using random integer function from random library to generate 10 random numbers for our list. The random.randint() function takes two parameter, starting and ending range of the random numbers. Next we will print the list to see the generated numbers in the list.

# Create a list of random numbers
my_list = [random.randint(1, 100) for _ in range(10)]

print(my_list)

Now, we'll define a function for Linear Search. The function will take two parameters, on will be the array or the list containing the numbers and the other will be the target element or number that the algorithm will search for. We will run a for loop that will iterate through the elements, or in this case the numbers, in the list. Inside the loop we will add a condition that compares our target number with the current element of list for each iteration. We will return the index of the target number if it is found. Otherwise we will return -1.

# Linear Search function
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Finally, let's perform the Linear Search on our list. First we define a target element or number that we will search in the list using linear search. Instead of defining it inside the code, we will take it as input from the user. Now we will call our linear search function and pass our list of number with the target number. It will return either the index of the number if it is found, or it wil return -1. So, we will add a conditional statement here. We will check if the returned value is not -1, which will mean the target number is found in the list and we will print the index of the number. The else condition will cover the case where the target number is not found in the list.

# Target element to search for
target_element = int(input("Eneter target number"))

# Call the Linear Search function
result = linear_search(my_list, target_element)

# Display the result
if result != -1:
    print(f"Element {target_element} found at index {result}.")
else:
    print(f"Element {target_element} not found in the list.")

Example with a List

We've coded a Linear Search function, and now we'll demonstrate how it works with our list. lets run the code.

Here, let's say we get the generated list that contains

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Lets give 5 as input for our target number. Our target element is found at index 4. We can also visually verify it from the output on the terminal. The output from the code will be

Element 5 found at index 4.

Let's try another case where we will search for a number that is not present in the list. Let's generate another list. Let's say this list contains

1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

We will set our target number as 15, which is not present in the list. Let's run the code. The code will output in the terminal that this number is not found in the list.

Element 15 not found in the list.

The search is performed step by step, comparing each element with the target element until a match is found.

Time Complexity

Let's look at the time complexity of the Linear search. Linear Search has a time complexity of O(n) in the worst case because it may need to search through all n elements in the list.

Summary

To recap, Linear Search is a simple algorithm for finding an element in a list. It checks each element one by one until a match is found. Thank you for reading this post on Linear Search 🙇‍♂️