Binary Search Variants: 7 Templates, Java + Python

The one algorithm every fresher says they know and still writes wrong under pressure. Starts with the invariant written out and the exact-match template, then a full page on the off-by-one decisions - lo <= hi versus lo < hi, why mid is written lo + (hi - lo) / 2, and when to write hi = mid instead of hi = mid - 1 - with a table of which combination goes with which variant. Then seven variants that actually get asked, each with a template, a worked example and a step-by-step trace: first occurrence, last occurrence and counting, lower bound, upper bound, search in a rotated sorted array, find a peak element, and binary search on the answer worked through Koko eating bananas. Ends with five mistakes and exactly how each one loops forever or misses the answer. 14 pages, PDF.