Binary Search Patterns

Binary search is not just for exact lookup. It also solves boundary and "answer search" problems.

Core invariant

Maintain a search interval where the answer still exists.

Common variants

• exact target search
• first/last true in a predicate space
• minimum feasible value

Practice

• Binary Search
• Search in Rotated Sorted Array
• Find Minimum in Rotated Sorted Array
• Median of Two Sorted Arrays