Binary Search Trên Đáp Án (Binary Search on Answer)

Bạn sẽ học được gì

Một bước nhảy vọt về tư duy: dùng tìm kiếm nhị phân không phải để tìm phần tử trong mảng, mà để tìm chính đáp án của bài toán. Khi đáp án có tính đơn điệu — qua một ngưỡng thì mọi giá trị một bên đều "được", bên kia đều "không" — ta nhị phân trên dải đáp án thay vì thử từng giá trị. Đây là một trong những kỹ thuật mạnh và hay bị bỏ sót nhất. Bài này khó 🔴 — hãy đi chậm.

1. Trực quan: cái công tắc chỉ bật một lần

Nhớ lại tìm kiếm nhị phân: nó hoạt động được vì mảng đã sắp xếp — mọi thứ bên trái nhỏ hơn, bên phải lớn hơn. Tính có trật tự đó cho phép loại nửa không gian mỗi bước.

Bây giờ hãy quên mảng đi. Tưởng tượng một dãy đáp án ứng viên, và với mỗi đáp án ta hỏi một câu "có / không" duy nhất qua hàm check(x). Điều kỳ diệu xảy ra khi câu trả lời có dạng một công tắc chỉ lật một lần:

Dap an x:     1    2    3    4    5    6    7    8
check(x):     K    K    K    C    C    C    C    C
                            ↑
                   nguong dau tien "C"

K = không thoả, C = thoả. Một khi đã C thì mọi x lớn hơn đều C; trước đó toàn K. Không có chuyện C rồi lại K rồi lại C. Đó là tính đơn điệu (monotonic). Và hễ có đơn điệu, ta nhị phân được: mỗi lần gọi check(mid), nếu C thì biết "ngưỡng nằm ở đây hoặc bên trái", nếu K thì "ngưỡng ở bên phải".

Ta không cần sắp xếp gì cả — bản thân bài toán đã sắp xếp sẵn các đáp án theo trục check.

2. Ý tưởng cốt lõi: ba câu hỏi

Để áp dụng kỹ thuật này, mọi bài toán đều quy về trả lời ba câu:

1. Đáp án nằm trong khoảng nào? Xác định lo và hi — cận dưới và cận trên hợp lý của đáp án.
2. Hàm check(x) là gì? Một hàm trả về đúng/sai: "với đáp án x này, ta có làm được không?".
3. Hàm đó đơn điệu theo hướng nào? Khi x tăng thì check đi từ sai sang đúng, hay từ đúng sang sai?

Nếu trả lời được cả ba, bài toán "tìm giá trị nhỏ nhất/lớn nhất thoả điều kiện" biến thành nhị phân trên đoạn lo..hi, chi phí chỉ O(log(hi − lo) × chi phí một lần check).

Thành phần	Vai trò
lo, hi	Không gian đáp án (không phải mảng dữ liệu)
check(x)	Lượng giá một đáp án ứng viên, trả về true/false
Đơn điệu	Điều kiện sống còn — không có nó thì không nhị phân được

3. Bài kinh điển: tốc độ ăn chuối của Koko

Koko có piles đống chuối và h giờ để ăn hết. Mỗi giờ nó chọn một đống và ăn k quả; nếu đống còn ít hơn k thì ăn hết đống đó rồi nghỉ phần giờ còn lại (không ăn sang đống khác trong giờ đó). Hỏi tốc độ k nhỏ nhất để ăn xong trong h giờ.

Hãy soi tính đơn điệu: nếu k càng lớn, Koko ăn càng nhanh → số giờ cần càng ít. Vậy hàm "k này có ăn kịp trong h giờ không?" đi từ không (k nhỏ, chậm) sang có (k lớn, nhanh) — đơn điệu! Ta tìm k nhỏ nhất cho ra "có".

• lo = 1 (ăn ít nhất 1 quả/giờ), hi = max(piles) (ăn nhanh nhất cũng chỉ cần bằng đống lớn nhất).
• check(k) = "với tốc độ k, tổng số giờ cần có nhỏ hơn hoặc bằng h không?". Số giờ cho một đống là ceil(pile / k) (làm tròn lên vì phần dư vẫn tốn trọn một giờ).

4. Chạy debug: Koko với piles=[3, 6, 7, 11], h=8

Bước qua vòng nhị phân tìm k nhỏ nhất. Theo dõi lo, hi, mid và kết quả check(mid).

🐞 Tìm tốc độ k nhỏ nhất (piles=[3,6,7,11], h=8)Bước 1/10

1lo, hi = 1, 11
2while lo < hi:
3  mid = (lo + hi) // 2
4  if can_finish(mid):
5      hi = mid
6  else:
7      lo = mid + 1
8return lo

Biến tại bước này

lo	1
hi	11

👉 Khoảng đáp án: từ 1 quả/giờ tới 11 (đống lớn nhất).

5. Code chạy được

Đang tải trình chạy code…

Để ý dòng mid = (lo + hi + 1) // 2 ở bài thứ hai. Khi tìm giá trị lớn nhất thoả mãn, ta phải làm tròn lên, nếu không vòng lặp có thể kẹt vô hạn lúc hi = lo + 1. Đây là cái bẫy kinh điển nhất.

6. Phân tích: độ phức tạp và những cái bẫy

Độ phức tạp: nhị phân trên đoạn đáp án rộng W = hi − lo tốn O(log W) lần lặp, mỗi lần gọi check tốn O(n) (duyệt dữ liệu). Tổng: O(n log W). So với việc thử từng đáp án O(n × W) thì nhanh hơn vượt bậc khi W lớn (hàng tỉ vẫn chỉ vài chục lần lặp).

Những cái bẫy phải nhớ:

• Hướng làm tròn. Tìm giá trị nhỏ nhất → mid = (lo + hi) // 2 (tròn xuống) và thu hi = mid. Tìm giá trị lớn nhất → mid = (lo + hi + 1) // 2 (tròn lên) và thu lo = mid. Sai hướng → lặp vô hạn.
• Xác định lo, hi sai. Cận trên phải đủ rộng để chắc chắn chứa đáp án, cận dưới phải hợp lệ.
• Hàm check không thật sự đơn điệu. Nếu đáp án dao động đúng-sai-đúng thì kỹ thuật này không áp dụng được — phải tìm cách khác.
• Quên rằng ta nhị phân trên ĐÁP ÁN, không phải trên mảng. Không cần sắp xếp dữ liệu đầu vào.

7. Mẫu nhận diện

Hãy nghĩ tới binary search trên đáp án khi đề bài có những dấu hiệu sau:

• Hỏi "giá trị nhỏ nhất / lớn nhất" sao cho một điều kiện nào đó được thoả.
• Có một ngưỡng: cứ vượt qua nó là điều kiện chuyển từ sai sang đúng (hoặc ngược lại) và không lật lại.
• Bạn dễ dàng kiểm tra một đáp án cụ thể (viết được check(x)) nhưng khó tính trực tiếp đáp án tối ưu.
• Từ khoá thường gặp: "tốc độ tối thiểu", "công suất nhỏ nhất", "chia thành k phần", "thời gian ít nhất để...".

Công thức ghi nhớ: "dễ kiểm tra một đáp án + đáp án đơn điệu theo điều kiện = nhị phân trên đáp án".

8. 🎮 Trò chơi: Nắm vững kỹ thuật

🎮 Binary search trên đáp ánCâu 1/4· Điểm 0· 🔥 0

Mấu chốt là hàm check(x) đơn điệu: qua một ngưỡng là lật từ sai sang đúng (hoặc ngược lại).

Độ phức tạp của kỹ thuật này (n phần tử, dải đáp án rộng W) là?

9. Quiz kiểm tra nhanh

📝 Quiz kiểm tra nhanh

1. Binary search trên đáp án khác tìm kiếm nhị phân thường ở điểm nào?

2. Vì sao bài "độ dài đoạn gỗ LỚN NHẤT" phải dùng mid = (lo + hi + 1) // 2?

3. Dấu hiệu đề bài gợi ý dùng kỹ thuật này là?

10. Hoàn thành

…

☑️ Tiếp theo: 3.3.1 — BFS (duyệt đồ thị theo chiều rộng, mở sang thế giới thuật toán trên đồ thị).