Binary Search

8 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   Look at the middle and throw away the half that can't hold the answer. n → n/2 → … → 1 takes about log₂ n looks: 20 for a million.

   #1
2. ↯use it when

   Sorted data, or any yes/no test that flips once (F F F T T T): first/last position, rotated arrays, peaks, "minimum speed that works".

   #2
3. { }template

   Exact: hi = n − 1, while (lo <= hi), move mid ± 1. Boundary: hi = n, while (lo < hi), hi = mid or lo = mid + 1, return lo.

   #3
4. O( )cost

   O(log n) time, O(1) space (iterative). On the answer: O(check × log range) — about 30 checks for a range of 10⁹.

   #4
5. !trap

   (lo + hi) / 2 overflows past 2³¹ − 1. Write lo + (hi − lo) / 2 — the JDK itself carried this bug for about nine years.

   #5
6. !trap

   lo = mid with a rounded-down mid loops forever when hi = lo + 1. Use lo = mid + 1, or round mid up.

   #6
7. !trap

   Arrays.binarySearch returns -(insertion point) − 1 when missing, and any copy among duplicates. Need first/last? Use lower/upper bound.

   #7
8. ✦pro tip

   Say the invariant out loud — "the answer is always in [lo, hi]" — and dry-run a 2-element array before you trust the loop.

   #8

Shaky on a card? Open the chapter or flip its recall cards.