Sedgewick & Wayne · §4.2 Binary search · lecture slide 11

Binary Search: Building the Search Tree

Write down the middle entry of every interval binary search can ever look at, and you get a tree. For N = 2^k − 1 entries it is perfectly balanced: the interval sizes go 2^k−1, 2^k−1−1, …, 3, 1. Every search miss is a top-to-bottom path: k levels, k compares, and k = lg(N+1) ~ lg N.

1 · Build the tree one level at a time

Each level holds the middles of the intervals left over by the level above. Removing the middle from an interval of size 2^k − 1 leaves two halves of size (2^k − 2)/2 = 2^k−1 − 1: the same form again, one power lower. The array below the tree shows the intervals of the newest level.

k (N = 2ᵏ − 1)

level = call	intervals	size of each	formula

2 · Every search is a path from the top

A search starts at the root (the middle of the whole array) and moves one level down per compare. A hit stops at the node holding the key. A miss runs off the bottom into an empty interval: it always costs all k levels.

key at index

compares (this search)–

every miss–

average hit–

lg N–

3 · The numbers: lg N versus N

Exact compare counts for N = 2^k − 1. A miss costs k = lg(N+1). A random hit costs a little less, because it can stop above the bottom level — but half of all nodes sit on the bottom level, so the average stays close to k − 1. Sequential search for comparison.

k	N = 2ᵏ − 1	lg N	binary: miss	binary: avg hit	sequential: avg hit	sequential: miss

Any N (not only 2ᵏ − 1)

For other N the halves differ by at most one entry, the tree is no longer perfect, and the worst case is ⌊lg N⌋ + 1 compares (the number of bits of N). Both formulas agree at N = 2^k − 1: ⌊lg 15⌋ + 1 = 3 + 1 = 4 = lg 16. The book derives the same ~lg N from the recurrence T(n) = T(n/2) + 1 (p. 535).

Companion to the binary-search session (lecture slides 1–19, book §4.2, p. 535 and Program 4.2.3, p. 539). Before: binary search arithmetic (slide 5) and the recursion trace (slide 10).