Learn Python – Linear Search in Python- Basic and advance

Python is one of the most popular and effective languages. It takes a few lines to execute the code, which makes it tons basic language. In this tutorial, we will study the linear search in Python. Searching is a technique to locate the particular thing is current or no longer in the given list.

There are two types of searching –

Linear Search

Binary Search

Both strategies are widely used to search an component in the given list.

What is a Linear Search?

Linear search is a technique of discovering elements inside a list. It is additionally called a sequential search. It is the simplest searching algorithm because it searches the desired factor in a sequential manner.

It compares each and each issue with the price that we are looking for. If both are matched, the thing is found, and the algorithm returns the secret is index position.

Concept of Linear Search

Let’s recognize the following steps to find the thing key = 7 in the given list.

Step – 1: Start the search from the first aspect and Check key = 7 with each factor of list x.

Step – 2: If aspect is found, return the index position of the key.

Step – 3: If element is not found, return thing is not present.

Linear Search Algorithm

There is list of n factors and key price to be searched.

Below is the linear search algorithm.

LinearSearch(list, key)  
  for each item in the list  
    if item == value  
      return its index position  
   return -1  

Python Program

Let’s understand the following Python implementation of the linear search algorithm.

Program

def linear_Search(list1, n, key):  
  
    # Searching list1 sequentially  
    for i in range(0, n):  
        if (list1[i] == key):  
            return i  
    return -1  
  
  
list1 = [1 ,3, 5, 4, 7, 9]  
key = 7  
  
n = len(list1)  
res = linear_Search(list1, n, key)  
if(res == -1):  
    print("Element not found")  
else:  
    print("Element found at index: ", res)  

Output:

Element found at index:  4

Explanation:

In the above code, we have created a characteristic linear_Search(), which takes three arguments – list1, size of the list, and number to search. We defined for loop and iterate every thing and evaluate to the key value. If issue is found, return the index else return -1 which potential element is no longer present in the list.

Linear Search Complexity

Time complexity of linear search algorithm –

Base Case – O(1)

Average Case – O(n)

Worst Case -O(n)

Linear search algorithm is appropriate for smaller list (<100) because it test every issue to get the desired number. Suppose there are 10,000 thing listing and desired aspect is reachable at the remaining position, this will devour plenty time via evaluating with each factor of the list.

To get the fast result, we can use the binary search algorithm.

We have discussed the basic thought of the linear search. In the next tutorial, we will study the 2d and most famous searching algorithm named Binary search.