liveBook · Manning

Binary search

As explained in Grokking Bayes

Binary search is an algorithm that repeatedly halves an ordered set of possibilities by testing a midpoint or threshold until the target is identified.

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

How Grokking Bayes covers it

How deep it goes
Explains midpoint selection, logarithmic reduction, entropy, and expected information gain, but stops short of general implementation details.
Examples
Demonstrates searching for an integer from 1 to 100 and compares balanced thresholds with unbalanced guesses and random guessing.
What it assumes
Assumes an ordered set of possibilities and teaches threshold questioning, halving, entropy, and information gain from the example.
What you can do after
Apply binary search by choosing midpoint thresholds and updating the remaining interval after each answer.
How it connects
Connects binary search with Bayesian experimental design, entropy, expected information gain, mutual information, and active learning.

Also explained in

Compare how 8 books explain binary search →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Grokking Bayes. The section links point to the parts of the book it draws on.