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 –
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
Let’s understand the following Python implementation of the linear search algorithm.
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)
Element found at index: 4
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.