ITPEC FE Morning October 2019 Question 8

20 — each comparison halves the items still in range, so the maximum is the number of halvings that bring 1 million down to one item.

• •2¹⁹ = 524,288, fewer than 1 million items
• •2²⁰ = 1,048,576, at least 1 million items
• •The base-2 logarithm of 1,000,000 is about 19.9, so at most 20 comparisons are needed

Answer (b)

Why not others:

• •(a) 15 — 2¹⁵ = 32,768: 15 comparisons cover only about 33 thousand items
• •(c) 25 — 2²⁵ is about 33.5 million: enough for 33 times as many items
• •(d) 30 — 2³⁰ is about 1.07 billion: the count for a thousand times as many items

Key rule: Binary search needs at most about log₂ n comparisons; since 2¹⁰ is about 1,000, every factor of 1,000 in n adds about 10 comparisons.

Algorithm and Programming · AI-written, may contain errors