Linear Search in Python

In the world of programming, searching for values efficiently is crucial. Many search algorithms use the “Linear Search” method. This article introduces linear search in Python. We’ll simplify the notion, clarify its inner workings, and teach you to confidently use this powerful approach. 

Whether you’re a beginner coder or a budding Pythonista, learn linear search and use it to search efficiently. Let’s delve into Python’s fascinating linear search!

If you are hyped up about the Python language, check out our course. Technogeeks can guide you through the roadmap of a Python developer. So, click on the link below and enter the awesome world of Python Programming!!

Click on the link below!

Python Training in Pune

What is Linear search

Linear search is like searching for a lost pen in a drawer full of pens. You go through each pen. Verify that is the one you want. You do this until you either find a match or reach the end of the drawer. 

Similarly, in linear search, we go through each element in a list one by one. You compare them to the value we want to find. If we find a match, we stop searching and note the position. If we haven’t found a match by the end, the value isn’t in the list. 

It’s a simple method that works even if the list is unsorted or has no specific order. Let’s see a step by step breakdown of how linear search works:-

How Linear Search works

• Imagine you have a list of numbers:- [8, 3, 12, 6, 10, 5]
• We want to find the position of the number 10 in the list using linear search.
• Start from the first element of the list, which is 8.
• Compare the first element with the target value (10). Since 8 is not equal to 10, move to the next element.
• Move to the next element, which is 3.
• Compare the second element with the target value. Since 3 is not equal to 10, move to the next element.
• Repeat this method to the end of the list. If we find a match, we will stop.

• At index 4, we find a match! The value 10 is present in the list.

• We can stop the search here and conclude that the value 10 is found at index 4.

If we don’t find the target value in the list, we continue the search until the end. If we got to the end of the list without finding the goal number, we can assume that the value 10 is not in the list.

Example of Linear Search in Python Program

Let’s see an example of a basic python program to understand the working of linear search in python.

Step 1: Defining the Linear Search Function

In this step, we define the “linear_search()” function. It takes two parameters:- 

1. “lst” – represents the list we want to search
2. “target” – which is the value we are looking for in the list

Step 2: Example List and Target Value

Here, we define an example list called my_list with the values [5, 8, 2, 10, 3]. We also set target_value to 10, which is the value we want to find in the list.

Step 3: Calling the Linear Search Function

We call the linear_search() function with my_list as the list to search and target_value as the value we are searching for. The returned index will be stored in the variable index.

Step 4: Linear Search Function Execution

Starting with the first item, the “linear_search()” method examines the list. We use list positions as integers. The “range()” and “len()” functions help us stay inside the list’s length.

Step 5: Checking for a Match

For each iteration of the loop, we compare the element at the current index (lst[i]) with the target value (target). If a match is found, we immediately return the index i. This means we have found the target value at that particular index, and the search can stop.

Step 6: Returning -1 if Target Value Not Found

If the loop finishes without a match, the target value was not in the list. -1 indicates that the target value is not in the list.

Step 7: Checking the Result and Printing the Output

Back in the main program, we check if the returned index is not equal to -1. 

If it’s not -1, it means that the target value was located in the list, and we print the message “The target value is at index” after the value of index. If the index is -1, we print the message “The target value is not found”.

In our example, the linear search successfully found the target value 10 at index 3 in the list. 

Therefore, the output will be:

The full code looks like this:

The output will look like this:

Complexity of Linear Search in Python

1. Time Complexity:
   • Best Case: O(1)
   • Average Case/Worst Case: O(n)
2. Space Complexity:
   • Constant: O(1)

In simple terms,

• The time taken increases as the list size (n) increases.
• The space complexity is O(1), indicating that the algorithm uses a fixed amount of memory, regardless of the list size.

Concluding Thoughts

Linear search is a simple algorithm, but it is not very efficient. Linear search takes proportionally longer for longer lists. The list may take a long time to discover the desired value.

There are more efficient algorithms for searching lists, such as binary search. However, linear search is a good algorithm to use if the list is small or if you do not need to find the target value quickly.

Here are some additional things to know about linear search:-

• Linear search is a sequential algorithm. This means that it searches the list in order, one element at a time.
• Linear search is a O(n) algorithm. This means that, time to search is directly proportional to the length of the list.
• Linear search is a good algorithm to use for small lists or for lists where you do not need to find the target value quickly.