Loop Control Statements in C Introduction to HTML How to use the Github API The image tag, anchor tag and the button tag Ordered and Unordered Lists in HTML The division tag HTML Forms Tables in HTML Introduction to C Programming Introduction to Python Varibles and Datatypes in Python Operators in Python Typecasting in Python Input and Output in Python If Else in Python Loops in Python Break, Continue and Pass in Python Python practice section 1 Lists in Python Tuple 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.