Smallest array forcing 7 probes

EasyProgramming & DSA~3m

Binary search on a sorted array of $n$ elements needs $\lceil \log_2(n+1) \rceil$ comparisons in the worst case. What is the smallest array size $n$ for which the worst case reaches exactly 7 comparisons?

Show hints (2)+

$\lceil\log_2(n+1)\rceil = 7$ means $6 < \log_2(n+1) \le 7$ .
Exponentiate: $64 < n+1 \le 128$ , so the smallest $n$ is at the low end.

Answer

Reveal answer →

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Practise free Unlock solutions

Asked at: Timed Mental-Math & Sequences, Game-Based Aptitude

Smallest array forcing 7 probes

Answer

Related questions