## Binary Search Example

Binary searches employ a divide and conquer approach for finding elements in ordered sets of data. Note that the set of data must be ordered for the technique to succeed. The approach is to divide the set of data into two halves. If the lowest element in the subset of data above the middle element is too large, it must follow that every element in the larger half of the set is also too large. The answer must lie within the lower half. The process repeats, dividing the data set in half each iteration.

Let $G$ be defined as the set of integers between 1 and .... Let $x$ be an integer in the set $G$, which defines the integer to be found. Then let integer $n$ represent the number of guesses required to find $x$. It then follows that the range of possible values for $n$ can be described such that \[ 1 \leq n \leq \lceil \log_2 |G| \rceil \text{,} \] where the expression $\lceil \log_2 |G| \rceil$ gives the ceiling of the value given by the base-2 logarithm of the total number of elements within $G$ (i.e., $|G|$ indicates the size, or mode, of $G$). 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.