Worst-Case Binary Search Comparisons

Each comparison in binary search halves the size of the remaining candidate range.

Find the smallest integer $k$ with $2^k\ge 1000$.

1. 1. Relate comparisons to halving the search space

   Binary search needs $\lceil {\log }_{2}n\rceil$ comparisons in the worst case to narrow $n$ candidates down to one.

   $$\lceil {\log }_{2}1000\rceil =10$$

Answer: 10