Linear Search in Python – A Detailed Overview

In this article, we will learn about the linear search algorithm, also known as sequential search. This algorithm is widely used for straightforward implementation. It starts from one end and goes through each list element until the desired element is found; otherwise, the search continues until the end of the dataset.

What is Linear Search Algorithm?

Linear search is a computer science algorithm for finding elements in a collection. In a linear search algorithm, each collection element is visited sequentially to find the desired element. Linear search is also known as sequential search.

This section will explain the Linear Search algorithm in proper working functionality.

Suppose a list of elements is given, and let’s say we want to find the 43 in the list of elements.

Data example : [33,44,99,33,43, 23,4,23] 

A step-by-step explanation of the example is given below.

Step 1: We search the list’s first element, ‘33’. We must compare ‘33’ with the target value ‘43’. Since ‘33’ is not equal to ‘43’. So, we move to the next element in the list.

Step 2: Next, we examine the second element, ‘44’. We have to compare ‘44’ with ‘43’. Again, ‘44’ does not match ‘43’, so we continue to the third element.

Step 3:  The third element in our list is ‘99. We will compare ‘99’ with ‘43’ and once more. They do not match. So, we proceed to the fourth element.

Step 4: The fourth element is ‘33’. We compare ‘33’ with ‘43’. As before, ‘33’ does not match ‘43’. So, we keep searching and move to the fifth element.

Step 5: We have reached the fifth element, ‘43’. We compare this element with our target value ‘43’. This time, we found a match. The value ‘43’ is indeed the element.

Step 6: We have found the target value and concluded our search. The linear search algorithm has successfully located the value ‘43’ at the index ‘4’ in the list.

Also Read: Python Tutorial for Beginners

Use Cases of Linear Search

Let’s look at some use cases of linear search algorithms:

• We can use linear search when the array size is not too big or constant. It is easier/faster to implement, thus saving development time.
• This algorithm is easy to understand and apply, so it can be used by developers to search for an element over a small array.

Python Linear Search Algorithm

In this section, we will see the Python linear search algorithm in Python. For a better understanding. Let’s look at the algorithm followed by the following code:

• Create the linear search() function.
• Declare the array, array length, and value to be found as three parameters.
• Initialise the for-loop
• Compare the value of the target key value with each element as you iterate.
• Return index if the element is present.
• Otherwise, the return element is absent.

Python Program for Linear Search

Let’s dive deep into the programming part of the Linear Search in Python.

Example 1: The example below is for searching for the index of 6 in the given array if it is present.

Output

Example 2: The example below searches for the index 9 in the given array if it is present.

Program

Output

Example 3: This example searches the index of 2 in the given array if it is present.

Program

Output

Time and Space Complexity

Let’s see the time and space complexity of the linear search algorithm.

Time Complexity

• Best Case: O(1): This is the best case of linear search algorithm because. It finds the first element in the list. In this scenario, the algorithm finds the target on the first comparison.

• Average Case O(n): This is the average case. The target value will be found somewhere in the middle of the list. The algorithm needs to check approximately half of the elements in the list. Leading to a time complexity of O(n/2), which simplifies to O(n).

• Worst Case O(n): The worst case occurs when the target value is either the last element in the list or not present at all. In this case, the algorithm must check all n elements in the list.

Space Complexity

• The linear search algorithm’s space complexity is O(1) because it uses a constant amount of extra space regardless of the size of the input list. The algorithm only requires a few variables (e.g., the index counter and the target value) to operate.

Conclusion

In this article, we learned that linear search in Python is a straightforward method for finding a target value within a list. This simplest algorithm suits small datasets or scenarios where the list is not sorted. However, its linear time complexity is O(n), which may not be the most efficient choice for large datasets compared to algorithms like binary search. Linear search remains a fundamental computer science concept and is a foundational example of basic searching techniques. Understanding the principle can pave the way for grasping more complex algorithms and data structures used in Programming and software development.