Binary search works on a half-open intervala[lo, hi): it includes a[lo] and excludes a[hi]. Everything in the code on the next slide — the empty test, mid, the two halves — is arithmetic on lo and hi. First watch the idea, then move lo and hi yourself.
1 · Watch binary search find "oscar"
Slide 4, animated as in the lecture video. The arrow points at the middle key of the part of the list that is still in play; each compare greys out the half that cannot contain the key. Try a miss, too.
Binary search (slide 4)
Keep the array in sorted order.
Examine the middle key.
If it matches, return its index.
If it is larger, search the half with lower indices.
If it is smaller, search the half with upper indices.
oscar?
compares0
still in play15
sequential search would need–
2 · The interval a[lo, hi) and its two halves
The sorted 15-name whitelist from the slides. The dashed slot at index 15 is past the end: hi may point there, because a[hi] is never looked at. Drag the sliders, or step into a half with the buttons.
0
15
lower half a[lo, mid)a[mid], compared with the keyupper half a[mid+1, hi)outside the interval
Upper half rule
3 · Why not (lo + hi) / 2?
Both formulas give the same mid — until lo + hi no longer fits into a Java int (largest value 2,147,483,647). Then the sum wraps around to a negative number (book Q&A, p. 559). This page computes with real 32-bit int arithmetic.
Companion to the binary-search session (lecture slides 1–19, book Program 4.2.3, p. 539). Next: the recursion trace (slide 10) and the search tree (slide 11).