Q.In the list : L = [7,-1,11,32,17,19,23,29,31,37,43] Determine the number of comparisons linear search takes to search for key = 43.
You're viewing a preview — the full solution, concept, methods & PYQ mapping are locked.
Start your 14-day free trial to unlock the full solution →Linear search compares the key sequentially with each element from the start until a match is found; for key = 43 at the last position, it requires 11 comparisons.
Why Linear Search and Counting Comparisons
Linear search is the simplest search algorithm: it examines each element in the list one by one, from left to right, until it finds the target key or exhausts the list. The number of comparisons is simply the position of the element (1-indexed) if found, or the length of the list if not found.
In this problem, we need to trace through the search process step by step to count how many times the algorithm compares the key with a list element.
The List and Target
Given:
- List:
L = [7, -1, 11, 32, 17, 19, 23, 29, 31, 37, 43] - Key to search:
43
The list has 11 elements, indexed 0 through 10 in Python.
Step-by-Step Trace
Linear search proceeds as follows:
| Comparison # | Index | Element | Match? |
|---|---|---|---|
| 1 | 0 | 7 | No |
| 2 | 1 | -1 | No |
| 3 | 2 | 11 | No |
| 4 | 3 | 32 | No |
| 5 | 4 | 17 | No |
| 6 | 5 | 19 | No |
| 7 | 6 | 23 | No |
| 8 | 7 | 29 | No |
| 9 | 8 | 31 | No |
| 10 | 9 | 37 | No |
| 11 | 10 | 43 | Yes |
The algorithm compares 43 with each element in turn. Since 43 is at the very last position (index 10), the search must check all 11 elements before finding it.
Python Implementation
Here's the linear search with a comparison counter:
def linear_search_with_count(L, key):
comparisons = 0
for i in range(len(L)):
comparisons += 1
if L[i] == key:
return i, comparisons # Return index and count
return -1, comparisons # Not found
L = [7, -1, 11, 32, 17, 19, 23, 29, 31, 37, 43]
key = 43 …
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.