Fundamental Algorithms8 sections · 291 units
Open in Course

Binary Search on the Answer

When you can't search an array, search the answer space.

Search for the answer in a range of possible values.

Pattern: If checking validity is O(f(n))O(f(n)) and validity is monotonic, binary search finds optimal in O(f(n)⋅log⁡(range))O(f(n) \cdot \log(range)).

Example: Minimum speed to finish trip in hh hours.

  • Answer in [1,maxDist][1, maxDist].
  • Check if speed vv finishes in hh hours.
  • Higher speeds valid if lower are. Monotonic.

Binary search on speed, check feasibility at midpoint.