Recap: Modified Binary Search

Name the predicate, check that it changes once, decide whether you want the first true or the last, and round mid to match.

Modified binary search applies wherever a yes-or-no predicate over a range of candidates changes only once, whether the candidates are indices, builds or possible answers. Naming the predicate comes first, then checking that it is monotone, then deciding whether the answer is the first true or the last; that decision fixes the moves, and the moves fix the rounding:

The forms of the search and what each needs
Search for	Predicate	Moves	mid rounded	Loop
First true	False, then true	True: high = mid; false: low = mid + 1	Down	low < high
Last true	True, then false	True: low = mid; false: high = mid − 1	Up	low < high
A value in a rotated array	Which half is sorted	Keep the half that holds the target	Down	low ≤ high
Smallest answer that works	This answer is feasible	As first true, over the answers	Down	low < high
Largest answer that works	This answer is feasible	As last true, over the answers	Up	low < high

The search makes O(log n) tests, each costing whatever the predicate costs, which over answers is usually a pass over the input: O(n log m). The loop that never ends comes from pairing low = mid with a rounded-down mid, and a predicate that turns false again after turning true gives a wrong answer with no warning.

Binary Search

← → move through sections and cards