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”.

**Related Posts:**

- Check Information Technology Books
- Apply for Python Internship
- Check Python Books
- Practice Programming MCQs
- Apply for Programming Internship