Linear Search Algorithm in Python

1. Introduction

Linear Search, also known as sequential search, is a simple search algorithm. It involves iterating over each element in a list and comparing it with the search key until a match is found or the end of the list is reached. It works on both sorted and unsorted lists but is less efficient than binary search on a sorted list.

2. Implementation Steps

1. Start from the first element in the list.

2. Compare the search key with the current element.

3. If they match, return the index of the current element.

4. If they don't match, move to the next element and repeat the process.

5. If the end of the list is reached and the key isn't found, return an indication that it's not present in the list.

3. Implementation in Python

def linear_search(arr, x):
    """Function to perform Linear Search on a list."""
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1
arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
x = 12
result = linear_search(arr, x)
if result != -1:
    print(f"Element {x} is present at index {result}")
else:
    print(f"Element {x} is not present in the list")

Output:

Element 12 is present at index 5

Explanation:

1. The linear_search function iterates over each element in the list arr.

2. For every element, it checks if it matches with the search key x.

3. If a match is found, it returns the index of that element.

4. If no match is found by the end of the list, it returns -1 indicating the element is not present in the list.

Linear Search has a time complexity of O(n) since in the worst case it might have to compare the search key with each element in the list. Despite its simplicity, it's not the most efficient searching algorithm for large lists, especially when the list is sorted.

Related Data Structures in Python


Comments

Post a Comment