Consider a sorted array of 10,00,000 elements. What is the maximum number of…

Concept

In binary search on a sorted array of n elements, each comparison discards half of the remaining candidates. The worst case therefore needs the smallest integer k of halvings that shrinks n down to a single element, i.e. the smallest k with 2k ≥ n. This is k = ⌊log2 n⌋ + 1.

Application

1. Here n = 10,00,000 = 1,000,000 elements.

2. Find the power of two that first reaches n: 219 = 5,24,288 (still below n) and 220 = 10,48,576 (now at or above n).

3. So the smallest k with 2k ≥ n is k = 20; equivalently ⌊log2 1,000,000⌋ + 1 = 19 + 1 = 20.

Cross-check

log2 1,000,000 ≈ 19.93, whose ceiling is 20, and 220 = 10,48,576 ≥ 1,000,000 while 219 = 5,24,288 < 1,000,000. Both routes agree: the worst case is 20 comparisons.