The Algorithm Design Manual Second Edition

2.6.1

Logarithms and Binary Search

Binary search is a good example of an O(log n) algorithm. To locate a particular

person p in a telephone book containing n names, you start by comparing p against

the middle, or (n/2)nd name, say Monroe, Marilyn. Regardless of whether p belongs

before this middle name (Dean, James) or after it (Presley, Elvis), after only one

comparison you can discard 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. By definition, this is exactly log

2

n. Thus, twenty comparisons suffice

to find any name in the million-name Manhattan phone book!

Binary search is one of the most powerful ideas in algorithm design. This power

becomes apparent if we imagine being forced to live in a world with only unsorted

O(n

3

)—i.e., a cubic algorithm.

---

2 . 6

L O G A R I T H M S A N D T H E I R A P P L I C A T I O N S

47

telephone books. Figure

2.4

shows that O(log n) algorithms are fast enough to be

used on problem instances of essentially unlimited size.