Binary Search Comparisons for 1024 Elements

Each yes/no comparison can at best halve the number of remaining candidate positions.

Find the smallest $k$ with $2^k\ge 1024$.

1. 1. Relate comparisons to halving the search space

   Each comparison partitions the remaining candidates into two roughly equal halves, so $k$ comparisons can distinguish at most $2^k$ positions.

   $$2^k\ge 1024$$

2. 2. Solve for k

   Since $2^{10}=1024$ exactly, ten comparisons suffice and are necessary in the worst case.

   $$k={\log }_2(1024)=10$$

Answer: 10