The Algorithm Design Manual Second Edition

Stop and Think: Importance of an Even Split

Problem: How many queries does binary search take on the million-name Manhat-

tan phone book if each split was 1/3 to 2/3 instead of 1/2 to 1/2?

Solution: When performing binary searches in a telephone book, how important

is it that each query split the book exactly in half? Not much. For the Manhattan

telephone book, we now use log

3

/2

(1, 000, 000)

≈ 35 queries in the worst case, not

a significant change from log

2

(1, 000, 000)

≈ 20. The power of binary search comes

from its logarithmic complexity, not the base of the log.