Binary search finds an unknown value by repeatedly asking a threshold question and discarding the half of an ordered range that cannot contain it. For a number between 1 and 100, asking whether it is greater than 50 leaves only 50 possibilities, whatever the answer. section 13.5 section 13.6
Use the procedure as a short loop:
- Choose the middle element of the remaining possibilities. section 13.6
- Ask whether the unknown is greater than that threshold. section 13.5
- Keep the half consistent with the answer and repeat until one possibility remains. section 13.7
The midpoint is efficient because each question halves the possibilities. Starting with 100 candidates therefore requires about log₂(100), or seven questions, to identify the answer. An unbalanced threshold may occasionally remove many candidates, but it more often removes only the smaller side. section 13.6
Why the middle is informative
Suppose the unknown number is uniformly distributed from 1 to 100. Asking whether it exceeds 50 creates two equally likely groups of 50. The expected information gain is one bit, because uncertainty falls from log₂(100) to log₂(50). The same idea evaluates every possible threshold and selects 50 as optimal. section 13.7
Figure 13.5 The procedure of binary search to find a number between 1 and 100. At each iteration, we ask whether the unknown number is greater than the element in the middle of the array, thus cutting the number of possibilities in half.

Follow the interval cuts from 1–100 to a single remaining value. section 13.6







