Δυαδική αναζήτηση στην απάντηση
Όταν το «γίνεται με ;» είναι μονότονο ως προς , βρίσκεις το μικρότερο που γίνεται σε ελέγχους.
Πότε
Το πρόβλημα ζητά «το ελάχιστο ώστε…» ή «το μέγιστο ώστε…», και είναι εύκολο να ελέγξεις αν ένα συγκεκριμένο αρκεί. Το σήμα είναι η μονοτονία: αν το αρκεί, αρκεί και κάθε μεγαλύτερο.
Η ιδέα
Έστω που είναι ψευδές, …, ψευδές, αληθές, …, αληθές στο . Κρατάμε την αναλλοίωτη: όλα κάτω από το είναι ψευδή, όλα πάνω από το αληθή. Κάθε βήμα κοιτά το μέσο και πετά τη μισή περιοχή. Μετά από βήματα μένει η απάντηση.
Στο Factory Machines το είναι «σε χρόνο οι μηχανές φτιάχνουν τουλάχιστον προϊόντα», δηλαδή . Αυτό είναι μονότονο ως προς και υπολογίζεται σε .
Παγίδες
- Το
(lo + hi) / 2υπερχειλίζει όταν τα όρια είναι κοντά στο . Τοlo + (hi - lo) / 2όχι. - Το άνω όριο να είναι σίγουρα εφικτό. Στο
Factory Machinesείναι , δηλαδή έως : χωράει σεlong long, αλλά το άθροισμα μέσα στο μπορεί να ξεπεράσει το όριο. Σταμάτα μόλις φτάσει το . - Γράψε το πρώτα και δοκίμασέ το μόνο του σε δύο τιμές. Τα περισσότερα λάθη είναι εκεί, όχι στον βρόχο.
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// Binary search on a monotone predicate.
// ok(x) is false, false, ..., false, true, true, ... on [lo, hi].
// Returns the first x in [lo, hi] with ok(x) true, or hi + 1 if there is none.
// Invariant: everything below lo is false, everything above hi is true.
template <typename F>
ll firstTrue(ll lo, ll hi, F ok) {
ll answer = hi + 1;
while (lo <= hi) {
ll mid = lo + (hi - lo) / 2;
if (ok(mid)) {
answer = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return answer;
}
Ελέγχθηκε σε 5.001 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Για εξάσκηση στο CSES
Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.
- Factory Machines · Sorting and Searching
- Array Division · Sorting and Searching
- Multiplication Table · Additional Problems I
Περισσότερα στο USACO Guide
- Binary Search · usaco.guide/silver/binary-search
Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.