Binary Search Problems

Binary search looks like a one-line algorithm — pick the middle, halve the range — but it's one of the most error-prone patterns in interviews. Off-by-one bugs in the boundary conditions are common; getting the loop invariants right takes practice. Master it once and you'll never get tripped up again.

There are two interview flavors. Direct search finds a target in a sorted array in O(log n) — straightforward but tested in many disguises (rotated sorted array, find first/last occurrence, peak element). Parametric search — sometimes called "binary search on the answer" — applies binary search to a continuous answer space rather than an array. Examples include Koko Eating Bananas, Capacity to Ship Packages, and Find Minimum in Rotated Sorted Array. The trick is identifying the monotonic predicate that lets you decide "is the answer ≤ x?" in linear time.

The Ratta binary-search track covers both flavors with worked examples in C++, Java, Python, and Go. Each problem highlights the loop invariant, the correct mid-point formula (avoiding integer overflow), and the boundary-condition discipline that distinguishes a working solution from a subtle bug.