Introduction to Python Programming Cycle of Python Varibles and Datatypes in Python Input and Output in Python Operators in Python Precedence of Operators in Python Typecasting in Python If Else in Python Loops in Python Break, Continue and Pass in Python Functions in Python Default Arguments and Keyword Arguments in Python Strings in python Lists in Python Tuple in Python Dictionary in Python Sets in Python List Comprehension in Python Unpacking Sequences in Python Higher Order Functions in Python Lambda Functions in Python Sieve of Eratosthenes Algorithm in Python Linear Search in Python Binary Search in Python Selection Sort in Python Bubble Sort in Python Insertion Sort in Python Merge Sort in Python

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.