Data Structures and Algorithms
A binary search is performed on 1,000 distinct values sorted in ascending order. If one comparison tells you whether the values are equal, smaller or larger, what is the maximum number of comparisons, counting both successful and unsuccessful searches?
- A10
- B32
- C500
Show answer and explanation
Answer: A. 10
Each comparison roughly halves the search range, and 2¹⁰ = 1024 ≥ 1000, so the range is used up after at most 10 comparisons (⌊log₂ 1000⌋ + 1 = 10). The complexity is O(log n), and even 1,000,000 values need at most 20 comparisons. 32 corresponds to √1000 ≈ 31.6, and 500 is close to the average for a linear search (about n/2). Keep in mind, though, that binary search needs sorted data, and sorting itself costs O(n log n).
- A. Correct. 2¹⁰ = 1024 ≥ 1000, so at most 10 comparisons are needed.
- B. This corresponds to √1000 and has nothing to do with binary search.
- C. This is close to the average number of comparisons for a linear search.