The average number of key comparisons done in a successful sequential search…
2025
The average number of key comparisons done in a successful sequential search in a list of length n is
- A.
log n
- B.
(n − 1)/2
- C.
n/2
- D.
(n + 1)/2
Attempted by 85 students.
Show answer & explanation
Correct answer: D
In a successful sequential search, the target element can be at any position from 1 to n with equal probability. The total number of comparisons is the sum of all possible positions: 1 + 2 + ... + n = n(n+1)/2. Dividing by the number of possible positions (n) gives an average of n(n+1)/(2n) = (n+1)/2 comparisons.