binary-search

When to use

Binary search works on any monotonic predicate, not just sorted arrays. Pattern: "find minimum X such that condition(X) is true" — binary search on the answer space.

Rules

• Use bisect.bisect_left/bisect_right for sorted-array insertion points
• For "minimize the maximum" or "maximize the minimum" problems, binary search on the answer and check feasibility
• ALWAYS use lo + (hi - lo) // 2 to avoid overflow
• When searching rotated arrays, check which half is sorted first
• NEVER binary search on unsorted data without a monotonic predicate

Complexity

Time: O(log n) — whenever you see "sorted" or "monotonic" in a problem, consider binary search.

Example

"Minimize maximum load" → binary search on answer space. Check if feasible(mid) divides into k groups each ≤ mid. Use lo + (hi - lo) // 2 to avoid overflow.