Binary Search Patterns Explained

Classic Binary Search

On a sorted array: find the index of target, or the first/last occurrence. Use lo, hi, and mid; adjust bounds to avoid infinite loops.

Binary Search on Answer

When the problem asks for "minimum/maximum value of X such that condition holds," the answer space is monotonic. Binary search on the answer and check with a helper function.

Examples

• Capacity to ship within D days.
• Koko eating bananas.
• Split array largest sum.

Rotated and Modified Arrays

• Rotated sorted: Find pivot, then binary search in the correct half.
• Search in rotated array: Compare mid with lo or hi to know which half is sorted.

Search Space Tricks

• Lower/upper bound: Use mid+1 or mid in updates to get first/last position.
• Real numbers: Binary search on range with tolerance (e.g. for square root).

Summary

Identify "sorted" or "monotonic" to apply binary search. Practice on Preplume(/) with tagged binary search problems.