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.