Q.Using linear search determine the position of 8, 1, 99 and 44 in the list:
[1, -2, 32, 8, 17, 19, 42, 13, 0, 44]
Draw a detailed table showing the values of the variables and the decisions taken in each pass of linear search.
Linear search checks each element sequentially until the target is found or the list ends; we trace the search for four values (8, 1, 99, 44) through the given list, showing index, comparison, and decision at each step.
Linear search is the simplest search algorithm: start at the beginning of the list and compare each element with the target value. If a match is found, return the position (index); if you reach the end without finding it, the element is not present. It requires no pre-sorting and works on any list, making it the natural choice when the data is unordered.
The list we are searching is:
data = [1, -2, 32, 8, 17, 19, 42, 13, 0, 44]
Positions (indices) run from to .
Search for 8
| Pass | Index | Element | Comparison (element == 8) | Decision |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 == 8 → False | Continue |
| 2 | 1 | -2 | -2 == 8 → False | Continue |
| 3 | 2 | 32 | 32 == 8 → False | Continue |
| 4 | 3 | 8 | 8 == 8 → True | Found at index 3 |
Result: 8 is found at position 3.
Search for 1
| Pass | Index | Element | Comparison (element == 1) | Decision |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 == 1 → True | Found at index 0 |
Result: 1 is found at position 0 (first element, immediate match).
Search for 99
| Pass | Index | Element | Comparison (element == 99) | Decision |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 == 99 → False | Continue |
| 2 | 1 | -2 | -2 == 99 → False | Continue |
| 3 | 2 | 32 | 32 == 99 → False | Continue |
| 4 | 3 | 8 | 8 == 99 → False | Continue |
| 5 | 4 | 17 | 17 == 99 → False | Continue |
| 6 | 5 | 19 | 19 == 99 → False | Continue |
| 7 | 6 | 42 | 42 == 99 → False | Continue |
| 8 | 7 | 13 | 13 == 99 → False | Continue |
| 9 | 8 | 0 | 0 == 99 → False | Continue |
| 10 | 9 | 44 | 44 == 99 → False | End of list reached |
Result: 99 is not found in the list.
Search for 44
| Pass | Index | Element | Comparison (element == 44) | Decision |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 == 44 → False | Continue |
| 2 | 1 | -2 | -2 == 44 → False | Continue |
| 3 | 2 | 32 | 32 == 44 → False | Continue |
| 4 | 3 | 8 | 8 == 44 → False | Continue |
| 5 | 4 | 17 | 17 == 44 → False | Continue |
| 6 | 5 | 19 | 19 == 44 → False | Continue |
| 7 | 6 | 42 | 42 == 44 → False | Continue |
| 8 | 7 | 13 | 13 == 44 → False | Continue |
| 9 | 8 | 0 | 0 == 44 → False | Continue |
| 10 | 9 | 44 | 44 == 44 → True | Found at index 9 |
Result: 44 is found at position 9 (last element, worst-case scenario for linear search).
Python Implementation
Here is the linear search function and the trace for all four values:
def linear_search(data, target):
for index in range(len(data)):
if data[index] == target:
return index # Found
return -1 # Not found
data = [1, -2, 32, 8, 17, 19, 42, 13, 0, 44]
targets = [8, 1, 99, 44]
for target in targets:
position = linear_search(data, target)
if position != -1:
print(f"{target} found at index {position}")
else:
print(f"{target} not found")
Output:
8 found at index 3
1 found at index 0
99 not found
44 found at index 9
Linear search has time complexity in the worst case (element at the end or absent) and in the best case (element at the start). For sorted data, binary search () is far more efficient, but linear search works on any list without preprocessing.
8 is at position 3, 1 is at position 0, 99 is not found, and 44 is at position 9.
Unlock everything free for 14 days
- Full step-by-step solutions
- Concept-first explanations
- Methods, shortcuts & mistakes
- PYQ mapping + timed mock tests
Full access for 14 days. No credit card required.