Binary search trên đáp án (Koko Eating Bananas) — khi nào nhị phân không phải trên mảng mà trên không gian giá trị?

Ý tưởng: Không tìm chỉ số trong mảng mà nhị phân trên dải đáp án khả dĩ. Với Koko, đáp án (tốc độ ăn k) nằm trong [1, max(piles)]. Tốc độ càng cao thì giờ ăn càng ít — đơn điệu — nên nhị phân được.

Dấu hiệu nhận dạng: câu hỏi dạng "giá trị nhỏ nhất/lớn nhất sao cho check(x) đúng", và check đơn điệu (đúng từ một ngưỡng trở đi). Ta nhị phân tìm ngưỡng đó.

function minEatingSpeed(piles: number[], h: number): number {
  const hours = (k: number) => piles.reduce((sum, p) => sum + Math.ceil(p / k), 0)
  let lo = 1, hi = Math.max(...piles)
  while (lo < hi) {
    const mid = (lo + hi) >> 1
    if (hours(mid) <= h) hi = mid // đủ chậm, thử nhỏ hơn nữa
    else lo = mid + 1            // quá chậm, phải ăn nhanh hơn
  }
  return lo
}

Độ phức tạp: O(n · log(max(piles))) thời gian, O(1) bộ nhớ.

Lưu ý: Cùng khuôn này giải "Capacity to Ship Packages Within D Days" và "Split Array Largest Sum" — chỉ đổi hàm check. Mấu chốt là xác định đúng cận [lo, hi] và chiều đơn điệu.

Idea: Don't search an index in an array — binary-search the range of feasible answers. For Koko, the answer (eating speed k) lies in [1, max(piles)]. Higher speed means fewer hours — monotonic — so binary search applies.

Recognition signal: questions phrased "smallest/largest value such that check(x) holds", with a monotonic check (true past some threshold). Binary-search for that threshold.

function minEatingSpeed(piles: number[], h: number): number {
  const hours = (k: number) => piles.reduce((sum, p) => sum + Math.ceil(p / k), 0)
  let lo = 1, hi = Math.max(...piles)
  while (lo < hi) {
    const mid = (lo + hi) >> 1
    if (hours(mid) <= h) hi = mid // slow enough, try smaller
    else lo = mid + 1            // too slow, must eat faster
  }
  return lo
}

Complexity: O(n · log(max(piles))) time, O(1) space.

Note: The same template solves "Capacity to Ship Packages Within D Days" and "Split Array Largest Sum" — only the check changes. The key is pinning the correct [lo, hi] bounds and the monotonic direction.