Phỏng vấn

Tìm kiếm nhị phân trên đáp án (Binary Search on Answer)

Khi đề bài yêu cầu tìm giá trị nhỏ nhất của mức cực đại (Min-Max) hoặc tốc độ tối thiểu để hoàn thành công việc đúng hạn, mảng đầu vào thường không hề được sắp xếp. Thay vì tìm kiếm trên chỉ số mảng, kỹ thuật tìm kiếm nhị phân trên đáp án đặt khung [lo, hi] trực tiếp lên miền giá trị của câu trả lời và dùng hàm kiểm tra đơn điệu để thu hẹp một nửa không gian ở mỗi bước.

Dấu hiệu nhận diện bài toán Tìm kiếm nhị phân trên đáp án

Trong bài toán tìm kiếm nhị phân cổ điển, bạn được cho một mảng đã sắp xếp tăng dần và cần tìm vị trí của phần tử target. Thế nhưng trong phỏng vấn Big Tech, những bài toán khó hơn như Koko Eating Bananas, Capacity To Ship Packages Within D Days hay Split Array Largest Sum đều đưa vào một mảng số nguyên hoàn toàn lộn xộn (thậm chí không được phép sắp xếp lại vì đề bài yêu cầu giữ nguyên thứ tự các ngày hoặc các đoạn liên tiếp).

Làm sao nhận ra ngay đây là bài toán Tìm kiếm nhị phân trên đáp án (Binary Search on the Answer)? Hãy chú ý ba tín hiệu đặc trưng sau:

  1. Cụm từ khóa Min-Max hoặc Max-Min: Đề bài hỏi "tốc độ nhỏ nhất để kịp giờ", "sức chứa tàu nhỏ nhất để chở hết hàng trong D ngày", "chia mảng thành k đoạn liên tiếp sao cho tổng lớn nhất trong các đoạn là nhỏ nhất", hoặc ngược lại "khoảng cách nhỏ nhất giữa hai con bò là lớn nhất".
  2. Đổi bài toán tối ưu thành bài toán quyết định (Decision Problem) dễ hơn rất nhiều: Nếu bắt tìm ngay tốc độ tối thiểu \(k\), bạn sẽ lúng túng; nhưng nếu người phỏng vấn cho sẵn một con số cụ thể \(k = 5\) và hỏi "Với tốc độ \(k = 5\), Koko có ăn hết chuối trong \(h\) giờ không?", bạn có thể kiểm tra ngay lập tức bằng một vòng lặp tham lam trong \(O(n)\).
  3. Tính đơn điệu của hàm kiểm tra check(x): Nếu tốc độ \(k\) đã đủ nhanh để ăn hết chuối đúng hạn (check(k) == True), thì mọi tốc độ lớn hơn \(k + 1, k + 2, \dots\) chắc chắn cũng kịp giờ (True). Ngược lại, nếu tốc độ \(k\) không kịp giờ (check(k) == False), thì mọi tốc độ chậm hơn \(1, 2, \dots, k - 1\) chắc chắn cũng không kịp (False).

Trước khi cài đặt, bạn nên xác nhận với người phỏng vấn các điều kiện biên của bài toán:

  • Giá trị câu trả lời luôn là số nguyên dương hay có thể là số thực?
  • Luôn tồn tại ít nhất một đáp án hợp lệ (ví dụ trong bài Koko, số giờ \(h\) luôn lớn hơn hoặc bằng số nải chuối \(n\): \(h \ge n\)) hay cần trả về -1 khi vô nghiệm?
  • Khi chia mảng thành các đoạn con, mỗi phần tử có bắt buộc thuộc đúng một đoạn liên tiếp không?
Ý chính

Mọi bài toán tìm kiếm nhị phân trên đáp án đều quy về một dãy trạng thái đơn điệu dạng False, False, ..., False, True, True, ... (khi tìm giá trị nhỏ nhất thỏa mãn) hoặc True, True, ..., True, False, False, ... (khi tìm giá trị lớn nhất thỏa mãn). Nhiệm vụ của bạn chỉ gồm 3 bước: chốt cận dưới lo, chốt cận trên hi chắc chắn khả thi, và viết hàm check(mid) trong O(n).

Binary Search on Answer: piles = [3, 6, 7, 11], h = 8 giờ k = 1..2 27h, 15h > 8 False k = 3 10h > 8h False (mid 2) k = 4 8h <= 8h True đầu tiên! k = 6 6h <= 8h True (mid 1) k = 11 4h <= 8h True (hi) Các bước thu hẹp [lo, hi]: [1, 11] (mid=6: True) → [1, 6] (mid=3: False) → [4, 6] (mid=5: True) → [4, 5] (mid=4: True) → Hội tụ tại k = 4
Koko ăn chuối: [3, 6, 7, 11], h = 8 Tìm tốc độ nhỏ nhất k ∈ [1..11] kịp 8 giờ k = 1..3: False k=3 mất 10h > 8h k = 4: True! 1+2+2+3 = 8h <= 8h k = 5..11: True (luôn kịp trong <= 8 giờ) Nhị phân hội tụ while (lo < hi): 1) [1, 11] → mid = 6 (6h: True) → hi = 6 2) [1, 6] → mid = 3 (10h: False) → lo = 4 3) [4, 6] → [4, 5] → Hội tụ lo = hi = 4
Hình 1. Không gian đáp án đơn điệu từ k = 1 đến k = 11 của bài toán Koko ăn chuối trên piles = [3, 6, 7, 11] với h = 8 giờ: điểm chuyển trạng thái từ False sang True đầu tiên nằm tại k = 4.

Thiết lập miền tìm kiếm [lo, hi] và công thức chia trần không dùng số thực

Xét bài toán Koko Eating Bananas: có n đống chuối với số quả lần lượt là piles[0..n-1] và người bảo vệ sẽ quay lại sau h giờ (\(h \ge n\)). Mỗi giờ Koko chọn một đống và ăn tối đa k quả; nếu đống đó có ít hơn k quả thì Koko ăn hết đống đó và nghỉ hết phần còn lại của giờ đó (không ăn sang đống khác trong cùng một giờ). Hỏi tốc độ ăn nguyên dương nhỏ nhất k là bao nhiêu?

  • Cận dưới lo: Tốc độ ăn tối thiểu phải là lo = 1 quả mỗi giờ (nếu k = 0 thì không bao giờ ăn xong và gây lỗi chia cho 0).
  • Cận trên hi: Vì mỗi giờ Koko chỉ được ăn nhiều nhất một đống, tốc độ nhanh nhất có ý nghĩa là bằng đúng đống chuối lớn nhất: hi = max(piles). Dù bạn có tăng tốc độ lên lớn hơn max(piles), mỗi đống vẫn tốn đúng 1 giờ như khi k = max(piles).
  • Hàm kiểm tra can_finish(k): Với tốc độ k, một đống có p quả sẽ cần \(\lceil p / k \rceil\) giờ. Tổng số giờ cần thiết là:

\[\text{hours}(k) = \sum_{i=0}^{n-1} \left\lceil \frac{\text{piles}[i]}{k} \right\rceil\]

Khi viết code trong C++17, Python hay Java 21, bạn nên tránh dùng hàm ceil((double)p / k) trên số thực dấu phẩy động vì với số nguyên lớn vượt \(2^{53} \approx 9 \cdot 10^{15}\), kiểu double chỉ có 53 bit phần định trị nên có thể làm tròn sai. Thay vào đó, hãy dùng công thức chia trần số nguyên chuẩn xác tuyệt đối (p + k - 1) / k.

Chạy tay từng bước trên piles = [3, 6, 7, 11], h = 8

Với piles = [3, 6, 7, 11] và h = 8, miền đáp án khởi tạo là lo = 1, hi = max(piles) = 11. Ta tìm giá trị k nhỏ nhất sao cho hours(k) <= 8 (và loại bỏ các tốc độ có hours(k) > 8):

Bước Đoạn [lo, hi] Điểm giữa mid Số giờ từng đống \(\lceil p_i / \text{mid} \rceil\) Tổng giờ và kết quả can_finish(mid) Cập nhật biên
1 [1, 11] mid = 6 \(\lceil 3/6 \rceil + \lceil 6/6 \rceil + \lceil 7/6 \rceil + \lceil 11/6 \rceil = 1 + 1 + 2 + 2\) 6 <= 8 → True (mid = 6 kịp giờ, thử giảm xuống < 6 hoặc giữ <= 6) Giữ mid làm ứng viên: hi = 6 (loại > 6)
2 [1, 6] mid = 3 \(\lceil 3/3 \rceil + \lceil 6/3 \rceil + \lceil 7/3 \rceil + \lceil 11/3 \rceil = 1 + 2 + 3 + 4\) 10 > 8 → False (mid = 3 quá chậm, mọi \(k \le 3\) đều hỏng) Loại bỏ nửa trái: lo = 3 + 1 = 4
3 [4, 6] mid = 5 \(\lceil 3/5 \rceil + \lceil 6/5 \rceil + \lceil 7/5 \rceil + \lceil 11/5 \rceil = 1 + 2 + 2 + 3\) 8 <= 8 → True (mid = 5 vừa khít 8 giờ) Giữ mid làm ứng viên: hi = 5 (loại > 5)
4 [4, 5] mid = 4 \(\lceil 3/4 \rceil + \lceil 6/4 \rceil + \lceil 7/4 \rceil + \lceil 11/4 \rceil = 1 + 2 + 2 + 3\) 8 <= 8 → True (mid = 4 cũng kịp trong 8 giờ!) Thu hẹp hi = 4 (loại > 4) → lo == hi == 4, dừng!

Khi vòng lặp while (lo < hi) kết thúc (tức lo >= hi), hai biên hội tụ tại lo = hi = 4, chính là tốc độ ăn chuối nhỏ nhất thỏa mãn yêu cầu.

Code mẫu C++17, Python và Java 21

Chương trình dưới đây cài đặt mẫu tìm kiếm nhị phân hội tụ while (lo < hi) (dừng khi lo >= hi) trên cả ba ngôn ngữ. Nếu chạy không kèm dữ liệu đầu vào, chương trình tự động kiểm tra bộ mẫu piles = [3, 6, 7, 11], h = 8 và in ra 4.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

bool can_finish(const vector<long long>& piles, long long h, long long k) {
    long long hours = 0;
    for (long long p : piles) {
        hours += (p + k - 1) / k;
        if (hours > h) return false;
    }
    return hours <= h;
}

long long min_eating_speed(const vector<long long>& piles, long long h) {
    long long lo = 1;
    long long hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (can_finish(piles, h, mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n = 4;
    long long h = 8;
    vector<long long> piles = {3, 6, 7, 11};
    if (cin >> n >> h) {
        piles.resize(n);
        for (auto& x : piles) cin >> x;
    }
    cout << min_eating_speed(piles, h) << '\n';
    return 0;
}

Hãy chú ý dòng dừng sớm if (hours > h) return false; ngay bên trong vòng lặp cộng dồn hours. Kỹ thuật nhỏ này vừa giúp chương trình thoát nhanh khi thử phải tốc độ k = 1 quá nhỏ, vừa ngăn chặn nguy cơ tổng hours vượt quá giới hạn kiểu số nguyên khi mảng có hàng trăm nghìn phần tử lớn.

Độ phức tạp thời gian và không gian

  • Thời gian: O(n log M), trong đó n là số phần tử của mảng piles và M = max(piles) là giá trị lớn nhất trong mảng. Số bước chia đôi miền [1, M] là \(\lceil \log_2 M \rceil\) (với \(M = 10^9\) chỉ mất khoảng 30 bước), và mỗi bước gọi hàm can_finish quét qua mảng tối đa n lần.
  • Bộ nhớ phụ: O(1) vì thuật toán chỉ dùng vài biến nguyên lo, hi, mid, hours và không cấp phát thêm cấu trúc dữ liệu phụ nào.

Áp dụng cùng một khung cho bài toán Chia mảng (Split Array Largest Sum)

Sức mạnh lớn nhất của mẫu Binary Search on Answer là tính chuyển giao trực tiếp giữa các bài toán nhìn bề ngoài rất khác nhau. Chẳng hạn với bài Split Array Largest Sum (hoặc Capacity To Ship Packages Within D Days):

  • Đề bài: Cho mảng số nguyên không âm nums và số nguyên m. Hãy chia nums thành m đoạn con liên tiếp sao cho tổng lớn nhất trong các đoạn là nhỏ nhất có thể.
  • Xác định [lo, hi]:
    • Mỗi phần tử phải nằm gọn trong một đoạn nào đó, nên sức chứa tối thiểu của một đoạn không thể nhỏ hơn phần tử lớn nhất: lo = max(nums).
    • Sức chứa lớn nhất cần xét là khi gom tất cả vào một đoạn duy nhất: hi = sum(nums).
  • Hàm kiểm tra can_split(limit): Duyệt từ trái sang phải, cộng dồn phần tử vào đoạn hiện tại chừng nào tổng chưa vượt quá limit; hễ cộng thêm phần tử mới mà vượt limit (cur_sum + x > limit) thì ngắt sang đoạn mới và tăng số đoạn pieces lên 1. Cuối cùng kiểm tra pieces <= m (hay pieces > m là thất bại).
Bài toán phỏng vấn Cận dưới lo Cận trên hi Ý nghĩa check(mid) (tính trong O(n)) Loại tìm kiếm
Koko Eating Bananas 1 max(piles) Tổng số giờ \(\sum \lceil p_i / \text{mid} \rceil \le h\) Tìm True đầu tiên (Min)
Ship Packages Within D Days max(weights) sum(weights) Số ngày gom hàng liên tiếp có tổng \(\le \text{mid}\) không vượt quá D Tìm True đầu tiên (Min)
Split Array Largest Sum max(nums) sum(nums) Số đoạn con liên tiếp có tổng \(\le \text{mid}\) không vượt quá m Tìm True đầu tiên (Min)
Minimum Time to Complete Trips 1 min(time) * totalTrips Tổng số chuyến \(\sum \lfloor \text{mid} / t_i \rfloor \ge \text{totalTrips}\) Tìm True đầu tiên (Min)
Magnetic Force Between Two Balls 1 pos[n-1] - pos[0] (sau khi sắp xếp pos tăng dần) Đặt tham lam các quả bóng cách nhau ít nhất mid có đủ m quả không Tìm True cuối cùng (Max)

Những lỗi làm vòng lặp bị treo vô hạn và cách tự kiểm tra

Khi cài đặt tìm kiếm nhị phân trên đáp án, 90% lỗi của ứng viên nằm ở việc ghép sai cặp công thức mid và phép gán thu hẹp biên:

  1. Vòng lặp vô hạn khi tìm cực đại (True cuối cùng) nhưng dùng mid = lo + (hi - lo) / 2:
    • Khi tìm giá trị nhỏ nhất (False ... False, True ... True), nếu check(mid) đúng thì ta gán hi = mid, nếu sai thì gán lo = mid + 1. Khi hi = lo + 1, mid = lo, hai nhánh cập nhật sẽ đưa về [lo, lo] hoặc [hi, hi], luôn giảm kích thước đoạn nên không bao giờ lặp vô tận.
    • Ngược lại, khi tìm giá trị lớn nhất (True ... True, False ... False), nếu check(mid) đúng thì ta giữ lo = mid, nếu sai thì gán hi = mid - 1. Lúc này, nếu vẫn viết mid = lo + (hi - lo) / 2, thì khi hi = lo + 1 ta có mid = lo và nhánh lo = mid sẽ giữ nguyên đoạn [lo, lo + 1] mãi mãi! Với bài toán Max-Min, bạn phải làm tròn lên: mid = lo + (hi - lo + 1) / 2 (hoặc dùng mẫu lưu biến best riêng với while (lo <= hi) dừng khi lo > hi).
  2. Đặt cận dưới lo = 0 trong bài toán chia cho mid: Nếu lo = 0 và hi = 1, mid sẽ bằng 0 và phép chia p / mid lập tức gây lỗi Divide by Zero.
  3. Đặt cận trên hi quá nhỏ ở bài toán thời gian: Trong bài Minimum Time to Complete Trips, nếu chỉ có 1 xe buýt tốn \(10^7\) giây/chuyến và cần chạy \(10^7\) chuyến, đáp án lên tới \(10^{14}\) (vượt xa INT_MAX). Bạn phải dùng kiểu 64-bit (long long trong C++, long trong Java) cho cả lo, hi, mid.

Để tự kiểm tra code trong lúc ôn luyện, bạn hãy viết một vòng lặp tuyến tính thử lần lượt k = 1, 2, ..., max(piles) và trả về số k đầu tiên thỏa mãn, sau đó so sánh với hàm nhị phân trên các ca biên:

  • Mảng chỉ có 1 đống chuối và h rất lớn: piles = [50], h = 100 (đáp án phải hạ về k = 1).
  • Số giờ h bằng đúng số đống chuối n: piles = [30, 11, 23, 4, 20], h = 5 (bắt buộc phải ăn mỗi đống trong 1 giờ nên k = max(piles) = 30).
  • Chỉ tăng thêm 1 giờ làm đáp án giảm mạnh: piles = [30, 11, 23, 4, 20], h = 6 (chỉ cần tách đống 30 thành 2 giờ nên k = 23).

Luyện ngay trên Big-O Coding

Hãy luyện tập ngay các bài toán tìm kiếm nhị phân từ cơ bản đến biến thể nâng cao trong lộ trình Coding Interview 150 dưới đây để nắm chắc phản xạ thiết lập hàm kiểm tra đơn điệu.

Câu hỏi thường gặp

Khi nào nên dùng mẫu while (lo < hi) và khi nào nên dùng while (lo <= hi) kèm biến ans?

Cả hai mẫu đều đúng và có cùng độ phức tạp. Mẫu while (lo < hi) (dừng khi lo >= hi) gọn hơn vì khi thoát vòng lặp, cả lo và hi đều trỏ thẳng vào đáp án duy nhất. Trong khi đó, mẫu while (lo <= hi) (dừng khi lo > hi) kèm biến ans (mỗi khi check(mid) đúng thì gán ans = mid rồi dịch hi = mid - 1 hoặc lo = mid + 1) có ưu điểm là hai nhánh cập nhật luôn dịch qua khỏi mid (mid - 1 và mid + 1), nên bạn không bao giờ sợ bị treo vòng lặp vô hạn dù tìm Min hay tìm Max.

Nếu mảng trong bài Split Array Largest Sum có chứa số âm thì có tìm kiếm nhị phân trên đáp án được không?

Không. Trong bài chia mảng thành các đoạn con liên tiếp, hàm kiểm tra tham lam can_split(limit) dựa trên tính chất: khi cộng thêm phần tử mới vào đoạn hiện tại thì tổng đoạn luôn không giảm. Nếu mảng có số âm, việc mở rộng đoạn thêm vài phần tử nữa có thể làm tổng đoạn giảm xuống dưới limit, khiến chiến lược ngắt đoạn tham lam trong O(n) bị sai. Khi có số âm, bài toán phải giải bằng quy hoạch động hoặc cấu trúc cây đoạn.

Làm sao tìm kiếm nhị phân trên đáp án khi câu trả lời là số thực (floating-point)?

Khi đáp án là số thực (ví dụ tìm bán kính nhỏ nhất hoặc vận tốc thực với sai số \(10^{-6}\)), bạn không dùng mid + 1 mà chạy một số bước cố định khoảng 60 đến 80 vòng lặp (for (int it = 0; it < 70; it++)), ở mỗi bước gán mid = (lo + hi) / 2.0, nếu check(mid) đúng thì hi = mid, ngược lại lo = mid. Vì mỗi bước chia đôi độ dài đoạn, sau 70 bước kích thước đoạn giảm đi \(2^{70} \approx 10^{21}\) lần, đạt độ chính xác tối đa của kiểu double mà không bao giờ bị treo do sai số làm tròn của biểu thức hi - lo > eps.

Muốn học bài bản cùng giảng viên?

Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483