# Linear Search Program in Python

Problem Description

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.

What is 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.

Linear Search Concept and Example

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.
Linear Search Algorithm
```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.

Program/Source Code

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:
else:
print('{} was found at index {}.'.format(key, index))```
Program Explanation

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.

Runtime Test Cases

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

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