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
- “Minimum/maximum X such that Y is possible.” — close to a giveaway.
- Checking a specific answer is much easier than finding the best one.
- The answer is a number in a known range, not a subset or arrangement.
- “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 lo24. 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 lo25. 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
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Binary Search on the Answer — the module
- Linear & Binary Search — Question Bank — the special case
- Modified Binary Search — the pattern
Software engineering
Infrastructure & security
Computer science
Hardware & engineering