Linear Search in Python

In this tutorial, we will learn the linear search in Python. we will write a code to search an element from a list. It compares each element to the criterion that we are finding. If all tiles are there, the element is located, and the algorithm returns the key’s index location.

so let’s see if you have a list and we have values let’s say

[5 ,8, 4 ,6, 9 ,2]

Suppose you want to search for a particular value within a list and search, for example, nine. How do we do that? We do have specific functions in Python using which you can do that, but what if you want to do it by yourself? You want to do it manually using a general loop. If you wish to search for an element, there are two scenarios here.

• The first scenario is the element that is searching for is in the list.
• The second scenario is the element that is searching for is not in the list.

Let’s go with the best scenario where you’re searching for nine, and it is in the list. Now how do we check? We have to run a loop, and you will check for each element.

Let’s say if you’re searching for nine, you will compare nine with the list’s first element, which is five in this case. Since it is not matching, you will go for the next element. We’ll compare that if this is not matching you will go for the next element that’s what you do and usually, do this till you find the element which is nine itself, which is the fifth element in the array with an index value for of course or the least, so let’s do it, so the element which you’re searching for is nine.

Let’s run through the method to decide the element key = 9 .

Python Linear Search Algorithm

There is list of n elements and key value to be searched.

Below is the linear search algorithm.

Search(list, n) 
while i<len(list):
   if list[i] == n: 
     return its index position 
   return -1 

Let’s we are implementing, and in this search, you will pass two things so you will pass a list and pass our values that are searching for if the value exists, you will print found else you will print not found.

Python Program for Linear Search

pos = -1
def search(list,n):
    i = 0
    while i<len(list):
      if list[i] == n:
        globals()['pos'] = i
        return True
      i = i + 1
    return False
list = [5,8,4,6,9,2]
n = 9
if search(list,n):
   print("Found at ",pos+1)
else:
   print("Not Found")

Output:

Python Linear Search Complexity

Time complexity of linear search algorithm

• Base Case – O(1)
• Average Case – O(n)
• Worst Case – O(n)