Sign in to watch this lesson
Algorithms - Sorting and Searching · 4:34
Binary Search on the Answer
When 'is the answer at most X?' is easy to check and switches from no to yes only once, we can binary search X itself. We solve a small Factory Machines instance (machines 3, 2 and 5 seconds, 7 items: the search tries 7, 10 and 8 seconds and answers 8), then see the same move in a min-max split, the k-th smallest entry of a multiplication table and a real-valued best average found with a fixed 100 halvings. Finally the traps: bounds that are not surely infeasible and feasible, a check whose sum overflows 64 bits (measured: a wrong answer near 10^18), and questions that are not monotone.
You will learn
- Recognise problems where 'is the answer at most X?' is monotone in X and cheap to check
- Choose bounds lo (surely infeasible) and hi (surely feasible) and binary search the first feasible X
- Apply the pattern to minimise-the-maximum splits, k-th smallest in an implicit set and real-valued answers
- Avoid overflow inside the check by capping sums, and reject non-monotone predicates