Binary search is a fast algorithm for searching in a sorted array S of keys.
To search for key q, we compare q to the middle key S[n/2].
If q appears before S[n/2], it must reside in the top half of our set;
if not, it must reside in the bottom half of our set.
By recursively repeating this process on the correct half,
we find the key in a total
of 
comparisons, a big win over the n/2 we expect
with sequential search.
This much you probably know. What is important is to have a sense for just how fast binary search is. Twenty questions is a popular children's game, where one player selects a word, and the other repeatedly asks true/false questions in an attempt to identify the word. If the word remains unidentified after 20 questions, the first party wins; otherwise, the second player takes the honors. In fact, the second player always has a winning strategy, based on binary search. Given a printed dictionary, the player opens it in the middle, selects a word (say ``move''), and asks whether the unknown word is before ``move'' in alphabetical order. Since standard dictionaries contain 50,000 to 200,000 words, we can be certain that the process will always terminate within twenty questions.
Other interesting algorithms follow from simple variants of binary search.
For example, suppose we have an array A consisting of a run of 0's,
followed by an unbounded run of 1's, and would like to identify the exact
point of transition between them.
Binary search on the array would provide the transition
point in
tests, if we had a bound n on the number of elements in the array.
In the absence of such a bound, we can test repeatedly at larger intervals
(A[1], A[2], A[4], A[8], A[16], )
until we find a first non-zero value.
Now we have a window containing the target and can proceed with
binary search.
This one-sided binary search finds the transition point p
using at most comparisons, regardless of how
large the array actally is.
One-sided binary search is most useful whenever we are looking for a key
that probably lies close to our current position.