Each call compares the key with the middle entry and either answers or calls itself on one half. On the way down the calls pile up on the call stack; on the way back the answer is returned through every call unchanged. Step through it one line at a time.
1 · Trace one search
The 15-name whitelist from the slides and the code from slide 8 (the same as the book's Program 4.2.3). The compareTo() values are the real ones Java would return; only their sign decides the branch.
Array
Code (slide 8)
Call stack · newest at the bottom
calls0
compares0
result–
On slide 10, > and < describe the key compared with a[mid] ("oscar" > "eve"). The code's cmp = a[mid].compareTo(key) has the opposite sign.
2 · The cost of every search
Run binary search for each of the 15 names (hits) and for one key in each of the 16 gaps around them (misses), on the array chosen above. Each chip shows the number of compares.
hits: the 15 names
misses: one key per gap (before alice, between neighbours, after wendy)
Companion to the binary-search session (lecture slides 1–19, book Program 4.2.3, p. 539). Before: binary search arithmetic (slide 5). Next: the search tree (slide 11). The shuffled array illustrates book Exercise 4.2.4: binary search on an unordered array.