Q.Consider a list of 15 elements: L=[2,3,9,7,-6,11,12,17,45,23,29,31,-37,41,43]. Determine the number of comparisons linear search makes to search for key = 12.
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 scans the list from index 0 onwards, comparing the key with one element at a time and stopping at the first match. The key 12 is at index 6, so the search makes comparisons with L[0] … L[6] — that is 7 comparisons (6 mismatches + 1 match) — and never looks at the remaining 8 elements.
The list and the key
L = [2, 3, 9, 7, -6, 11, 12, 17, 45, 23, 29, 31, -37, 41, 43]
key = 12
The list has 15 elements. It is unsorted, which is exactly why linear search (and not binary search) is the applicable technique here.
The algorithm
LINEARSEARCH(L, n, key)
Step 1: SET i = 0
Step 2: WHILE i < n REPEAT Steps 3 to 4
Step 3: IF L[i] == key THEN return i // found
Step 4: SET i = i + 1
Step 5: return -1 // not found
Every execution of Step 3 is one comparison.
Step-by-step trace
| Comparison # | Index i | L[i] | Is L[i] == 12 ? | Action |
|---|---|---|---|---|
| 1 | 0 | 2 | No | move on |
| 2 | 1 | 3 | No | move on |
| 3 | 2 | 9 | No | move on |
| 4 | 3 | 7 | No | move on |
| 5 | 4 | −6 | No | move on |
| 6 | 5 | 11 | No | move on |
| 7 | 6 | 12 | Yes | found — return index 6, stop |
The loop terminates at index 6. Elements at indices 7–14 (17, 45, 23, 29, 31, −37, 41, 43) are never compared.
Code with a comparison counter
def linear_search(L, key):
comparisons = 0
for i in range(len(L)):
comparisons += 1
print("Comparison", comparisons, ": is L[", i, "] =", L[i], "equal to", key, "?",
"YES" if L[i] == key else "no")
if L[i] == key:
return i, comparisons
return -1, comparisons
L = [2, 3, 9, 7, -6, 11, 12, 17, 45, 23, 29, 31, -37, 41, 43]
index, comparisons = linear_search(L, 12)
print("\nKey found at index :", index)
print("Number of comparisons :", comparisons)
Output
Comparison 1 : is L[ 0 ] = 2 equal to 12 ? no
Comparison 2 : is L[ 1 ] = 3 equal to 12 ? no
Comparison 3 : is L[ 2 ] = 9 equal to 12 ? no
Comparison 4 : is L[ 3 ] = 7 equal to 12 ? no
Comparison 5 : is L[ 4 ] = -6 equal to 12 ? no
Comparison 6 : is L[ 5 ] = 11 equal to 12 ? no
Comparison 7 : is L[ 6 ] = 12 equal to 12 ? YES
Key found at index : 6
Number of comparisons : 7
The rule to remember: if linear search finds the key at index i (0-based), it makes exactly i + 1 comparisons. Here i = 6, so 6 + 1 = 7.
Where this sits in the complexity picture
| Case | Key position | Comparisons | …
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.