Programs

# Linear Search in Python Program: All You Need to Know

## Introduction

To search for an element in a given data structure, we implement certain algorithms to efficiently carry out our tasks. These kinds of algorithms are known as Searching Algorithms. Some commonly used Searching Algorithms are – Linear Search Algorithm, Binary Search Algorithm, Jump Search Algorithm, Interpolation Search Algorithm, etc.

Out of all these algorithms, Linear Search Algorithm is the oldest and the simplest searching algorithm. In this article, we will be learning how Linear Search Algorithm is implemented on a data structure and also be looking into the Python 3 implementation of the algorithm.

## Procedure

Linear Search Algorithm is the first searching algorithm starters often learn when they start learning data structures and algorithms. Let us take an example and see how Linear Search Algorithm can be implemented.

Let us consider we have the following data in a Python List and we want to search for the value = 30.

 21 65 7 30 132 77 16 54

0                 1                 2                  3               4                     5                 6                7

• Step 1: We consider the first value, i.e. 21 from the list, and then compare that value with our search value, i.e. 30. Since it is not equal, we move on to the next value in the list.
• Step 2: Now, we consider the second element, i.e. 65, and compare it with value = 30. Since it is not equal, we again move on to the next element.
• Step 3: We have now 7 on our list. On comparing the two elements, we find 7 is not equal to 30. Hence, we move to the next element.
• Step 4: We have now element 30 on our list. We compare 30 with value = 30. Since 30 is equal to 30, we have found our desired element in the list. We can then print a message saying the element has been found and then return the index value = 3 of that element for further calculations.

As you can see, this is an iterative procedure, so this iteration will continue as long as the desired element is found or it reaches the end of the list. If it reaches the end of the list, but there is no such element found in the list, it can display a message saying, no such element is present.

So, this is the Linear Search Algorithm, and surely you must have found it out to be very simple.

## Time Complexity

1. Worst Case – O(n) where n is the number of elements in a list. For the worst case, the element is at the end of the list, the loop needs to be executed for n times.
2. Best Case – O(1). For the best case, the element is found in the first position in the list.
3. Average Case – O(n). Summation of all the time taken for each element in the list and getting the average of all the elements in the list gives us O(n) time complexity.

## Python 3 Implementation

Now let us look at how we can implement this algorithm in Python. Now when we give input as 30, let us see the output: If we enter a value that is not present in the list, for example, value = 980, let us see what the output is: That is indeed the correct output as there is no 980 element present in the list.

Also Read: Data Scientist Salary in India

## Conclusion

In this article, we have looked into what is a Linear Search Algorithm and also studied in detail how to search for a certain element from a list using the Linear Search Algorithm. Lastly, we also saw how we could practically implement the Linear Search Algorithm using Python 3 as a language and get our desired output.

If you are interested in Data Science, you must check out IIIT-B and upGrad’s Online Data Science Courses which has been carefully crafted for working professionals and offers numerous case studies, hands-on workshops, 1-on-1 mentorship, and much more.

### What are the space and time complexities of Linear Search?

Linear Search is an efficient approach when the data is not sorted but can be a little expensive in terms of time. The time and space complexities depend upon how much time the compiler takes to execute the program and how much memory the program consumes respectively. Below are the time and space complexities of the linear search.

### Differentiate between linear search and binary search?

The prominent differences between the linear search and binary search are as follows:
Linear Search:
1. The average time complexity of the linear search is O(n).
2. It is best suited for unsorted data.
3. Performs an iterative approach.
4. The key is present at the start of the list in the best case.
Binary Search:
1. The average time complexity of the binary search is O(log(n)).
2. It is best suited for sorted data.
3. Performs the divide and conquer approach.
4. The key is present at the middle of the list in the best case.

### What is the interpolation search?

Interpolation search is the optimized version of binary search where the average time to find the key element is O(log(log n)). In binary search, we always look up to the middle of the array. But in this method, the search can go to different locations depending on where the key is located. For instance, if the key is located near the last element of the array, the search will start from the end of the array. ## Prepare for a Career of the Future

### Data Science Skills to Master  