Binary Search

CodeMusings home

Let $G$ be defined as the set of integers between 1 and ##. Let $x \in G$ be defined as the integer to be found. In a binary search, the set of possible answers is halved after each guess. Therefore, we can deduce the maximum number of required guesses: \[ 1 \leq x \leq \lceil \log_2 |G| \rceil \] In this case, we have a maximum of 0 possible guesses.

The binary search simulation below will use a pseudo-random number generator to pick a number within the set $G$, after which the algorithm runs until the target integer is found. The results will be displayed, as well as a visual representation of eliminating incorrect integers. Click the simulate link multiple times to run more simulations. One interesting thing to note is that, once you begin seeing integers being fully enumerated, the search has reduced the possible number of answers below 100.

Start simulation.