Binary Search

AI Generated

Halve the search space every step, so $O(\log n)$. What it actually needs is a monotonic predicate — some check that goes false, false, …, true, true — not necessarily a sorted array.

• On the array — find a value, or the first/last index satisfying a condition.
• On the answer — guess an answer, check in O(n) whether it's feasible, shrink the range. The tell is "minimize the maximum" or "maximize the minimum" (Koko eating bananas).
• On the partition — split two arrays so everything left is ≤ everything right (median of two sorted arrays).

The gotchas are all in the boundaries: use mid = l + (r - l) / 2 to avoid overflow, and decide deliberately whether the loop ends on l > r or on a found condition, and whether a bound moves to mid or mid ± 1.