Pattern-Binary-Search-on-Answer

Pattern — Binary Search on Answer (Parametric Search)

Trend 2026 — Most-asked

Pattern này được liệt vào “trending pattern” của FAANG 2025-2026 (Educative, Design Gurus). Khả năng ra interview của Meta/Google/Amazon là rất cao.

Khi nào dùng

Signal phrases

• “Minimize the maximum X” / “Maximize the minimum X”
• “Find the smallest K such that …”
• “What is the optimal capacity?” / “shortest time” / “fewest splits”
• Search space của ĐÁP ÁN có monotonic property với một predicate feasible(x).

Template

function findMinFeasible(): number {
  let lo = /* lower bound đáp án */, hi = /* upper bound đáp án */;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (feasible(mid)) hi = mid;       // có thể nhỏ hơn → thu hẹp
    else                lo = mid + 1;  // không feasible → tăng
  }
  return lo;
}

3 bước thiết kế

1. Xác định search space: đáp án x nằm trong [lo, hi] nào? (vd: capacity ∈ [max(weight), sum(weight)])
2. Define feasible(x): với capacity x, có ship trong D ngày được không? Trả về boolean.
3. Verify monotonic: nếu feasible(x) = true thì feasible(x+1) = true? (lớn hơn → dễ hơn) → “find min feasible”. Hoặc ngược lại.

Top problems (FAANG hot)

Bài	LC	Difficulty
Koko Eating Bananas	LC #875	Medium
Capacity to Ship Within D Days	LC #1011	Medium
Split Array Largest Sum	LC #410	Hard
Find K-th Smallest Pair Distance	LC #719	Hard
Magnetic Force Between Balls	LC #1552	Medium
Minimum Time to Complete Trips	LC #2187	Medium
Minimum Number of Days to Make m Bouquets	LC #1482	Medium
Median Two Sorted Arrays	LC #4	Hard (variant)
Path with Minimum Effort	LC #1631	Medium

Pitfalls

1. Sai search space: nếu chọn lo = 0 cho Koko, feasible(0) = false (∞ ăn) → vô hạn. Phải lo = 1.
2. Sai monotonic direction: nhầm “feasible từ true sang false” với ngược lại → infinite loop hoặc đáp án sai.
3. Integer overflow: mid = (lo+hi)/2 overflow khi hi là 1e9.
4. Edge case: feasible trên lo = hi (search space 1 điểm) phải return đúng.

Cách approach trong interview

1. Brute force với loop trên đáp án — show O(answer × N).
2. Nhận ra monotonicity → đề xuất binary search → giảm về O(log answer × N).
3. Code template + walk through feasible.

→ Nguồn lý thuyết: 04-Advanced-Binary-Search