Learn about Linear Search in Python

Introduction

Linear Search is one of the simplest search techniques in the data structure. This is also called sequential search which is commonly used to find the index of an element in the unsorted list or array. 

You may be wondering why I called unsorted list or array. Because there is another search technique called binary search which only works for sorted arrays or lists and this algorithm is best for it. That's why linear or sequential search is usually used for sorted arrays or lists.

In this tutorial, you'll learn about linear search in python.

How does linear search work?

• Traverse 0th to the nth element using for loop.
• In Each iteration, for loop checks, if the search item is matched with the current list or array data.
• It matches then, it returns the index of the current array element.
• If it doesn't match, iteration move to the next item.
• If no match is found until the nth element, it returns -1 or a False message.

Code

'''Linear search program in python'''
def LinearSearch(arr, key):
    for i in range(0, len(arr)):
        if arr[i] == key:
            return i
    return -1

if __name__=="__main__":
    arr = [5, 9, 8, 3, 6, 1]
    key = int(input("Please enter the key: "))
    result = LinearSearch(arr, key)
    if result == -1:
        print("Sorry!, The key is not found!")
    else:
        print(f"The key has found at index no. {result}")

Output

Please enter the key: 8
The key has found at index no. 2

Complexity Analysis

In the worst-case scenario, the iteration goes to the nth element and there is no need to use any extra spaces for the linear search algorithm. Let's conclude.

Time Complexity of Linear Search

Average Case: O(n)

Worst Case: O(n)

Space Complexity of Linear Search

Space Complexity: O(1)