ITPEC FE Morning October 2019 Question 8
Source exam: ITPEC FE Morning October 2019Topic: Basic Theory & Math
ITPEC FE Morning October 2019 — Question 8 of 80
Binary Search — Maximum Comparisons — find max comparisons for 1 million items.
Binary search halves the search space each step, so the maximum number of comparisons is ⌈log₂(n)⌉.
- •
n = 1,000,000 - •
log₂(1,000,000) ≈ 19.93 - •Round up →
20 - •Verify:
2²⁰ = 1,048,576 ≥ 1,000,000✓
Why not others:
- (a) 15 — 2¹⁵ = 32,768, far too small
- (c) 25 — 2²⁵ = 33,554,432, overshoots significantly
- (d) 30 — 2³⁰ = 1,073,741,824, way too large
Key rule: Max comparisons = ⌈log₂(n)⌉. For powers of 2, it's the exponent itself.
AI-generated — may contain errors
The original exam layout is preserved in the image so diagrams, formulas, tables, and code remain accurate.
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.