AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Mediumsearchingcomplexity

~75s

Comparisons in a binary search

What is the maximum number of comparisons binary search makes on a sorted array of 1000 elements?

Show the answer and the worked solution

Correct answer: B.

10

Worked solution

  1. Each comparison halves the search space, so k comparisons can distinguish at most 2^k positions.
  2. 2^9 = 512 is less than 1000, so nine comparisons are not enough.
  3. 2^10 = 1024 is more than 1000, so the maximum needed is 10.

Answer: 10.

The idea

The bound is ⌊log₂ n⌋ + 1 comparisons. Doubling the array adds exactly one comparison, which is why binary search stays usable at any realistic size.

Shortcut. Halve until nothing is left: 1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 is ten probes.

Common trap. 9 is ⌊log₂ 1000⌋ without the +1; 2⁹ = 512 positions are too few to cover 1000.

Data Structures & Algorithms

29 of 40

Level

Medium

Target time

~75s

PreviousNext
AI InterviewGet started

Comparisons in a binary search — Aptitude Question

Comparisons in a binary search: What is the maximum number of comparisons binary search makes on a sorted array of… Answer and worked solution on CodeKairo.

Question

What is the maximum number of comparisons binary search makes on a sorted array of 1000 elements?

Options

  1. 9
  2. 10
  3. 11
  4. 500
Show the answer and the worked solution

Correct answer: B. 10

Worked solution

  1. Each comparison halves the search space, so k comparisons can distinguish at most 2^k positions.
  2. 2^9 = 512 is less than 1000, so nine comparisons are not enough.
  3. 2^10 = 1024 is more than 1000, so the maximum needed is 10.

Answer: 10.

The idea

The bound is ⌊log₂ n⌋ + 1 comparisons. Doubling the array adds exactly one comparison, which is why binary search stays usable at any realistic size.

Shortcut. Halve until nothing is left: 1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 is ten probes.

Common trap. 9 is ⌊log₂ 1000⌋ without the +1; 2⁹ = 512 positions are too few to cover 1000.

All Data Structures & Algorithms questions · placement mock tests