Micro-questions over the parametric search module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. The reframing

1. State the Koko problem.

Answer

piles of bananas, hours. She picks a speed ; each hour she eats from one pile, finishing early if it has fewer than left. What is the smallest that finishes every pile within hours?

2. Why do the obvious approaches fail?

Answer

Deriving a formula is defeated by the ceilings; trying every speed from 1 upward is .

3. What different question do you ask instead?

Answer

“Does speed work?” — which is easy: sum and compare to .

4. What does tabulating that answer reveal?

Answer

F F F T T T T T… — one flip, and it never flips back, obviously so since eating faster can never take longer.

5. State the realisation about binary search itself.

Answer

That pattern is the only thing binary search has ever required. A sorted array searched for a target is the same pattern in disguise — a[i] >= target is F F F T T T. The sortedness was never the point; it was just a way of guaranteeing the flip.


B. The vocabulary

6. What is binary search on the answer?

Answer

Also parametric search — applying binary search to the range of possible answers, rather than to an input collection.

7. What is a predicate here?

Answer

A function from a candidate answer to true/false: “is this candidate good enough?”. Writing it is usually the easy part; recognising that you should is the hard part.

8. What is a monotone predicate, and what is its status?

Answer

One whose value, read across the range in order, changes at most once — F...FT...T or T...TF...F. It is the precondition for the whole technique, and it must be proved rather than assumed.

9. What is the flip point?

Answer

The single position where the predicate changes value. Finding it is the problem.

10. What determines the total cost?

Answer

The feasibility check multiplied by the log: an check over a range of size gives .

11. What must be true of lo and hi?

Answer

Both must be justified. lo must definitely fail (or be the minimum conceivable), and hi must definitely succeed.

12. Is a huge answer space a problem?

Answer

No — .


C. Recognising it

13. Give the four signals in order of reliability.

Answer
  1. “Minimum/maximum X such that Y is possible.” — close to a giveaway.
  2. Checking a specific answer is much easier than finding the best one.
  3. The answer is a number in a known range, not a subset or arrangement.
  4. “Minimise the maximum” or “maximise the minimum”.

14. What is the check that saves you?

Answer

Tabulate the predicate over a small instance. If you see F F F T T T you are done. Anything else, stop — the technique does not apply.


D. Worked problems

15. Split array — what is the predicate?

Answer

“Can we split into at most parts with no part exceeding cap?” — greedily fill parts until they would overflow, then count.

16. Justify both bounds for split array.

Answer

lo = max(nums): no capacity below the largest single element can work, since that element must fit somewhere. hi = sum(nums): one part containing everything always works.

17. What happens if you set lo too low here?

Answer

Here it still produces the right answer but wastes iterations — and in other problems it breaks the monotonicity at the bottom of the range.

18. Integer square root — what is the predicate and which direction is it?

Answer

x*x <= n, which is T...TF...F — the other monotone direction, needing the largest true template.

19. Linear versus binary steps for isqrt at ?

Answer

A billion steps against 61. The answer space is huge and its logarithm is not.

20. How does the loop change for a real-valued answer?

Answer

There is no “next” value, so the condition becomes a tolerance: while hi - lo > 1e-12. Reaching tolerance over range takes iterations.

21. Why must you never write while lo < hi with floats?

Answer

Floating-point values can fail to converge to equality, giving an infinite loop. Use a tolerance or a fixed iteration count — 100 is ample for any double.


E. The two templates

22. In the largest-true template with lo = mid, lo = 4, hi = 5 and a floor midpoint — what happens?

Answer

mid is 4, so lo = mid leaves lo = 4, hi = 5: nothing changed, and the loop runs forever.

23. Write Template A (smallest true).

Answer
while lo < hi:
    mid = lo + (hi - lo) // 2        # FLOOR
    if predicate(mid): hi = mid      # might be the answer: keep it
    else:              lo = mid + 1  # definitely not: discard it
return lo

24. Write Template B (largest true).

Answer
while lo < hi:
    mid = lo + (hi - lo + 1) // 2    # CEIL
    if predicate(mid): lo = mid      # might be the answer: keep it
    else:              hi = mid - 1  # definitely not: discard it
return lo

25. State the rule that generates both.

Answer

The branch that keeps mid must not be the branch that can fail to make progress. Round the midpoint away from the variable that gets assigned mid — A assigns to hi so round toward lo (floor); B assigns to lo so round toward hi (ceil).

26. Why lo + (hi - lo) // 2 even in Python?

Answer

Habit. In C++, Java or Rust lo + hi can overflow — the bug that sat in the JDK’s binarySearch for nine years.


F. Monotonicity

27. What goes wrong if the predicate does not flip exactly once?

Answer

Halving can discard the half containing the answer, giving a confidently wrong result.

28. Give the counterexample.

Answer

” is prime” over : F T T F T F T F. No single flip point — “the smallest prime ” cannot be found by halving.

29. Prove monotonicity for Koko.

Answer

If speed finishes in time, so does , because for every pile. Eating faster never takes longer.

30. Prove it for split array.

Answer

If capacity admits a valid split into parts, so does — the same split is still valid, since every part still fits.


G. Traps

31. Bounds too tight — what happens?

Answer

If the true answer lies outside [lo, hi] you get the nearest endpoint, silently.

32. Bounds too loose — when is it actually harmful?

Answer

Rarely — it costs a few extra iterations — unless the predicate is undefined outside the valid range, such as dividing by a speed of zero.

33. When does the technique not pay?

Answer

When the feasibility check is expensive. Total cost is — if the check is , optimise the check first.

34. What is the “answering the wrong question” trap?

Answer

The template returns the flip point. “Smallest speed that works” and “largest speed that fails” differ by one, and both are easy to return by accident.

35. Summarise the technique in one sentence.

Answer

When checking an answer is easy but finding it is not, binary search the answer space on a predicate you have proved flips exactly once.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Searching