Linear Search Program in Python

Write a Python program that implements linear search. The program accepts a list and a key as input, and it finds the index of the key in the list using linear search.

Linear search is a simple search algorithm used to find the position of a target value within a list. It sequentially checks each element until a match is found or the list is exhausted.

Here’s a step-by-step example of how linear search works in Python for the given list [5, 4, 3, 2, 1, 10, 11, 2] and the target value “1“:

• Step 1: Start with the given list: [5, 4, 3, 2, 1, 10, 11, 2], and set the target value to 1.
• Step 2: Begin at the first element of the list, which is 5.
• Step 3: Compare 5 with the target value (1). Since they don’t match, move to the next element, which is 4.
• Step 4: Compare 4 with the target value (1). Since they don’t match, move to the next element, which is 3.
• Step 5: Compare 3 with the target value (1). Since they don’t match, move to the next element, which is 2.
• Step 6: Compare 2 with the target value (1). Since they don’t match, move to the next element, which is 1.
• Step 7: Compare 1 with the target value (1). They match! Return the index of the element, which is 4.
• Step 8: The linear search is successful, and the index 4 is returned.

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

This algorithm iterates through each element in the list and compares it with the key. If a match is found, it returns the index of the element. If no match is found after iterating through the entire array, it returns -1 to indicate that the key was not found.

Here is the source code of a Python program to implement linear search. The program output is shown below.

def linear_search(alist, key):
    """Return index of key in alist. Return -1 if key not present."""
    for i in range(len(alist)):
        if alist[i] == key:
            return i
    return -1
 
alist = input('Enter the list of numbers: ')
alist = alist.split()
alist = [int(x) for x in alist]
key = int(input('The number to search for: '))
 
index = linear_search(alist, key)
if index < 0:
    print('{} was not found.'.format(key))
else:
    print('{} was found at index {}.'.format(key, index))

1. Create a function linear_search that takes a list and key as arguemnts.
2. The list and key is passed to linear_search.
3. If the return value is -1, the key is not found and a message is displayed, otherwise the index of the found item is displayed.

Time Complexity: O(n)
The time complexity of the linear search algorithm is O(n), where n is the size of the input list. This is because in the worst case, the algorithm may need to iterate through all n elements of the list to find the key or determine its absence.

Space Complexity: O(1)
The space complexity of the linear search algorithm is O(1), as it does not require any additional space that grows with the input size. The algorithm only uses a fixed amount of memory to store variables, regardless of the size of the input list.

Test Case 1: In this case, we use the linear search algorithm to find the position of element, and the elements are entered in random order i.e {5 4 3 2 1 10 11 2} and the element to be searched is “1”.

Enter the list of numbers: 5 4 3 2 1 10 11 2
The number to search for: 1
1 was found at index 4.

Test Case 2: In this case, we use the linear search algorithm to find the position of element, and the elements are entered in random order i.e {3 8 5 6} and the element to be searched is “2”.

Enter the list of numbers: 3 8 5 6
The number to search for: 2
2 was not found.

To practice programs on every topic in Python, please visit “Programming Examples in Python”.