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.