Binary Search

Binary Search finds a target in a sorted search space by repeatedly halving the interval.

KEY TAKEAWAYS

• Sorted Input: The input must be sorted or monotonic. This is the primary trigger for Binary Search.
• Logarithmic Time: Reduces $O(n)$ linear scan to $O(log n)$.
• Transition Point: Many binary search problems can be reframed as finding a boundary between two properties (e.g., true vs false, small vs big).

1. TRANSITION-POINT RECIPE

To avoid off-by-one errors and infinite loops, use this robust recipe:

1. Define is_before(val): A helper function that returns true for elements in the first half (the "before" region) and false for the second half (the "after" region). The range must be monotonic: all trues must come before all falses.
2. Initialize Boundaries: Set l and r to cover the entire possible range.
   • Invariant: l is always in the "before" region, and r is always in the "after" region.
3. Loop Condition: while r - 1 > l. This ensures we stop when l and r are adjacent (the transition point).
4. Update Logic:
   • Calculate mid = (l + r) // 2.
   • If is_before(mid), move l = mid (keep l in "before").
   • Else, move r = mid (keep r in "after").
5. Return: Return l or r depending on whether you need the last element of the "before" region or the first element of the "after" region.

2. GRID FLATTENING

For 2D grid problems that require binary search or iteration as if it were a 1D array, map coordinates [r, c] to a flat index i:

• 2D to 1D: i = r * Cols + c
• 1D to 2D: r = i // Cols, c = i % Cols

3. GUESS-AND-CHECK (BINARY SEARCH ON ANSWER)

If an optimization problem asks for a minimum or maximum value satisfying a condition, and the condition is monotonic (if $x$ works, then all $y > x$ work, or vice versa), you can binary search on the answer space.

• Range: Define the minimum and maximum possible values for the answer.
• Check Function: Write a check(value) function that returns true if the value is valid.
• Search: Use binary search to find the boundary where check(value) flips from true to false.