Căutare binară pe răspuns: capacitatea minimă
O firmă de curierat are o dubă și o listă de colete care trebuie livrate în ordine, în cel mult D zile. Ce capacitate minimă trebuie să aibă duba? Nu cauți într-o listă, ci cauți binar răspunsul: încerci o capacitate, verifici dacă ajunge, și înjumătățești intervalul. E unul dintre cele mai puternice tipare de interviu.
Problema
Coletele au greutățile [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] și trebuie livrate în ordinea dată, în cel mult 5 zile. În fiecare zi duba încarcă colete la rând, cât timp nu depășește capacitatea. Care e cea mai mică capacitate care permite livrarea în 5 zile?
Scrie zile_necesare(colete, capacitate) (câte zile sunt necesare cu o capacitate dată, coletele în ordine) și capacitate_minima(colete, zile), care caută binar cea mai mică capacitate între max(colete) și sum(colete) pentru care livrarea se…
- zile_necesare: încarcă la rând, începe o zi nouă când următorul colet nu mai încape.
- capacitate_minima: st, dr = max(colete), sum(colete), bucla while st < dr, dr = mij dacă ajunge, altfel st = mij + 1.
- Trebuie să apară: 15, 6, 3, 32.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan