Linear Search in Python

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 function linear_Search(), which takes three arguments - list1, length of the list, and number to search. We defined for loop and iterate each element and compare to the key value. If element is found, return the index else return -1 which means element is not 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 suitable for smaller list (<100) because it check every element to get the desired number. Suppose there are 10,000 element list and desired element is available at the last position, this will consume much time by comparing with each element of the list.

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

We have discussed the basic concept of the linear search. In the next tutorial, we will learn the second and most popular searching algorithm named Binary search.