Căutare binară pe răspuns: condiția de monotonie

Căutarea binară nu se limitează la găsirea unei valori într-un vector sortat. Poate găsi și cel mai mic răspuns care satisface o condiție, dacă răspunsurile posibile au o ordine potrivită. Condiția esențială este monotonia verificării.

Ce este un predicat monoton

Un predicat este o funcție care răspunde adevărat sau fals. Pentru căutarea celui mai mic răspuns fezabil, vrem ca valorile mici să dea fals, apoi de la o anumită frontieră toate valorile să dea adevărat. După primul adevărat nu trebuie să apară din nou fals.

Nu este suficient ca răspunsul numeric să fie într-un interval. Trebuie demonstrat că posibilitatea de a rezolva problema se păstrează când deplasezi limita în direcția aleasă.

Exemplu cu o capacitate

Ai colete cu greutăți pozitive, în ordine fixă, și vrei să le transporți în cel mult D zile. Pentru o capacitate C, verifici dacă poți împărți secvența în cel mult D grupuri consecutive, fiecare cu sumă cel mult C.

Dacă o anumită capacitate funcționează, orice capacitate mai mare funcționează folosind aceeași împărțire. Acesta este argumentul de monotonie. Pentru greutățile 2,3,4 și D=2, capacitatea 4 nu ajunge, dar capacitatea 5 permite grupurile [2,3] și [4].

Pentru greutățile 2,3,4 și cel mult două zile, capacitatea 4 cere trei zile, iar capacitatea 5 permite [2,3] și [4]. Orice capacitate mai mare rămâne fezabilă.Mărește schema ↗

Verificatorul trebuie să fie și el corect

O verificare uzuală adaugă colete în ziua curentă până când următorul nu mai încape, apoi începe o zi nouă. Greutățile pozitive și ordinea fixă justifică această prelucrare pentru numărul minim de zile la capacitatea dată.

Dacă un colet depășește capacitatea, verificarea trebuie să întoarcă fals. Nu îl plasa într-o zi care ar depăși limita. Căutarea binară nu repară un verificator care acceptă soluții imposibile.

Margini și progres

Cea mai mare greutate este o limită inferioară naturală, iar suma tuturor greutăților este o capacitate fezabilă când D este cel puțin unu. Calculează suma într-un tip suficient de larg. La fiecare pas, intervalul trebuie să se micșoreze.

Testează răspunsul la fiecare margine și un interval cu o singură valoare. Separat, verifică pe intrări mici toate capacitățile și compară prima fezabilă cu rezultatul căutării. Astfel verifici atât predicatul, cât și gestionarea frontierelor.

Continuă cu căutarea binară, metoda greedy și complexitatea.

Întrebări frecvente

Ce este căutarea binară pe răspuns?

O metodă care caută frontiera dintre răspunsuri nefezabile și fezabile, folosind o verificare adevărat-fals. Nu este necesar să existe un vector explicit cu toate răspunsurile.

Ce înseamnă un predicat monoton?

Pentru căutarea minimului fezabil, verificarea este falsă până la o frontieră și adevărată după ea. Nu poate reveni la fals când mărești candidatul; această proprietate justifică eliminarea unei jumătăți.

Care este complexitatea căutării binare pe răspuns?

Dacă intervalul are R valori candidate, sunt necesare O(log R) verificări. Timpul total include costul fiecărei verificări, nu doar numărul pașilor căutării.