Data Structures and Algorithms
A linear search compares the elements of an array of 100 distinct values one by one from the front to find a target. If the target is always in the array and is equally likely to be at any position, what is the average number of comparisons?
- AAbout 7
- B50.5
- C100
Show answer and explanation
Answer: B. 50.5
If the target is at position k, the search makes k comparisons, so the average is (1 + 2 + … + 100) / 100 = 50.5, or (n + 1)/2 in general. The best case (target at the front) takes 1 comparison and the worst case (target at the end) takes 100; both the average and the worst case are proportional to n, so the complexity is O(n). About 7 corresponds to log₂ 100 ≈ 6.6, the number of steps of a binary search, which cannot be used unless the data is sorted.
- A. This is close to the maximum for a binary search, not the average for a linear search.
- B. Correct. (1 + 2 + … + 100)/100 = 50.5, or (n + 1)/2 in general.
- C. This is the worst case, when the target is at the end.