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.

Get curriculum highlights, career paths, industry insights and accelerate your technology journey.

Download brochure

How to Perform Linear Search in Python?

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.

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.

def search(a, l, x):
for i in range(l):
if (a[i] == x):
return i
return -1
a = [33, 44,99,33,43,234,23]
print("The given array is ", a)
x = 43
print("Element to be searched is ", x)
l = len(a)
ind = search(a, l, x)
if(ind == -1):
print("Element Not Found")
else:
print("Element is at index ", ind)

Output

The given array is [33, 44, 99, 33, 43, 234, 23]
Element to be searched is 43
Element is at index 4

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

Program

def search(a, l, x):
for i in range(l):
if (a[i] == x):
return i
return -1
a = [12, 43, 34, 45, 23]
print("The given array is ", a)
x = 9
print("Element to be searched is ", x)
l = len(a)
ind = search(a, l, x)
if(ind == -1):
print("Element Not Found")
else:
print("Element is at index ", ind)

Output

The given array is [12, 43, 34, 45, 23]
Element to be searched is 9
Element Not Found

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

Program

def search(a, l, x):
for i in range(l):
if (a[i] == x):
return i
return -1
a = [99, 34, 65, 43, 223]
print("The given array is ", a)
x = 43
print("Element to be searched is ", x)
l = len(a)
ind = search(a, l, x)
if(ind == -1):
print("Element Not Found")
else:
print("Element is at index ", ind)

Output

The given array is [99, 34, 65, 43, 223]
Element to be searched is 43
Element is at index 3

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.

FAQs

What is a linear search?

Linear search is a simple searching algorithm that sequentially checks each list element until it finds the target value or reaches the end of the list.

How does linear search work?

Linear search works by iterating through each element in a list and comparing each element with the target value. If the target value is found, it returns the element's index; otherwise, it continues until the end of the list.

When should I use a linear search?

The time complexity of a linear search is O(n), where n is the number of elements in the list. This means the time it takes to search increases linearly with the list's size.

What is the worst-case time complexity for linear search?

The worst-case time complexity for linear search is O(n). which occurs when the target value is the last element in the list or not present at all.

What are the advantages of linear search?

The advantages of linear search include its simplicity and ease of implementation and its ability to work on unsorted lists without requiring additional preprocessing.

Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.