Binary search on 1000: the worst case
Binary search runs on a sorted array of 1000 distinct elements (indices 0-999). Each step probes the middle index mid = (lo + hi) // 2 and stops when it finds the target. The worst case is 10 probes. For how many of the 1000 elements does a successful search take exactly 10 probes?
Show hints (2)+
- A successful search for an element takes as many probes as its depth in the implied balanced search tree.
- Depths 1-9 can hold at most elements.
Answer
Reveal answer →Final answer
489
Create a free account to see the full worked solution and track your progress.
Interview format: Hedge Fund Quant, Systematic & Data-Driven Trading