Comparisons in a linear search — Aptitude Question
Comparisons in a linear search: The array A is 1-indexed. How many times is the comparison A[i] == key evaluated? Answer and worked solution on CodeKairo.
- Topic: Pseudocode
- Section: Programming MCQs
- Difficulty: Medium
- Time target: 105 seconds
Question
The array A is 1-indexed. How many times is the comparison A[i] == key evaluated?
Integer A[1..8], i, key, cmp
Set A = {12, 7, 9, 25, 4, 18, 25, 3}
Set key = 25
Set cmp = 0
Set i = 1
While i <= 8
Set cmp = cmp + 1
If A[i] == key Then
Break
End If
Set i = i + 1
End While
Print cmpOptions
- 3
- 4
- 7
- 8
Show the answer and the worked solution
Correct answer: B. 4
Worked solution
- i = 1 compares 12 against 25: cmp = 1, no match.
- i = 2 compares 7: cmp = 2. i = 3 compares 9: cmp = 3.
- i = 4 compares 25 against 25: cmp = 4 and the Break fires.
- The second 25 at position 7 is never reached, so 4 is printed.
Answer: 4.
The idea
Linear search costs one comparison per position examined and stops on the first hit. The duplicate later in the array is there to tempt you into counting all the way to position 7.
Shortcut. A search that stops on the first hit makes exactly as many comparisons as that hit's position, and 25 first appears at position 4.
Common trap. 3 counts only the failed comparisons before the match; cmp is increased before the test, so the matching comparison counts too.