Binary Search in Action
Binary search is a fast algorithm for searching in a sorted array of keys.
To look up a name in a telephone book
with n names, you start by comparing the name that you want
with the middle or (n/2)nd name, say \em Monroe, Marilyn.
Regardless of whether what you are looking someone before this middle name
(Dean, James) or after it (Presley, Elvis), after this first
comparison you can forever disregard one half of all the names
in the book.
The number of steps the algorithm takes equals the number of times we
can halve n until only one name is left.
Thus twenty comparisons suffice to find any name in the million-name Manhattan
phone book!
The power of binary search and logarithms is one of the most
fundamental idea in the analysis of algorithms.
This power becomes apparent if we
imagine living in a world with only unsorted telephone books.
The following animation of the first two stages
of binary search is provided for your amusement.
An MPEG-2 video of binary search
and the full video tapes
are also available.
