Linear Search in Python

Searching means checking for a value in a sequence e.g. list, tuple, dict, etc, and locating where it is present. Linear search is the simplest searching algorithm. It works by comparing each element of the sequence with the element we want to search. Hence, it is also called sequential search.

Implementation

We will iterate through the list and check whether the key(element to be searched) matches any element of the list. If yes, then we break out of the loop and print the index where it was found. Otherwise, we compare the key with the next element until the key is found or we reach the end of the list. If the key is not found, we will print that the key is not found. 

def linear_search(arr,key):
    for i in range(len(arr)):
        if key==arr[i]:
            return i

    # if we reach the end of the list and the key is not found, we return -1.
    return -1

arr=[1,3,2,5,7]
key=int(input("Enter the key to search: "))

found_at=linear_search(arr)

if found_at!=-1:
print("Key found at index ",i)
else:
print("Key not found")
Output
Enter the key to search: 3
Key found at index 1

Enter the key to search: 6
Key not found
Time Complexity : O(n) where n is the size of the list
Explanation : We run a loop from i=0 to len(arr)-1. At every index, we check whether the arr[i] equals the key or not. When the key is found, we break out of the loop. The key may be present at the last index or it may not be present. Hence, in that case, the loop will run a maximum of n times where n is the number of elements present in the list. So the time complexity will be O(n).
Space Complexity : O(1) no additional space used.

Advantages and Disadvantages

Advantages :
  1. Easy to understand.
  2. Can work on both sorted as well as unsorted arrays.
Disadvantages :
  1. Compares each array element with the element to be searched. Hence, it takes linear time to search.