Part 3.5b ~40 min read Intermediate

Chapter 3.5b: Binary Search on Answer

English translation of this chapter is coming soon. Please refer to the Chinese version for now.

Content Outline

3.5b.1 What is Binary Search on Answer?

  • From Brute Force to Binary Search

3.5b.2 Three Key Elements of Binary Search on Answer

  • Answer within a Fixed Range
  • Easy-to-Implement Check Function
  • Monotonicity
  • Two Forms of Monotonicity

3.5b.3 Integer Binary Search Templates

  • Template A: Find the Maximum Satisfying Value (Maximization)
  • Template B: Find the Minimum Satisfying Value (Minimization)
  • Why lo + 1 < hi instead of lo < hi?

3.5b.4 Complete Example: Cutting Wood

3.5b.5 Example: Maximize the Minimum (Placing Cows)

3.5b.7 Ternary Search (Finding Extrema of Unimodal Functions)

Common Mistakes

Exercises

  1. Cutting Ropes (Floating-Point Binary Search)
  2. Array Partitioning (Minimize Maximum)
  3. K-th Smallest Element in a Sorted Matrix
  4. Placing Cows (Maximize Minimum Distance)
  5. Jumping Rocks (NOIP 2015)
  6. Optimal Ratio (Fractional Programming)
  7. Minimize Maximum Cost (Binary Search + Graph)
  8. Minimize Total Waiting Time (Binary Search + Greedy)