De ce contează?
Când vrei să tai o scândură, nu îți cioplești singur un ferăstrău: iei unul din atelier, ascuțit și verificat de mii de oameni înaintea ta. La fel în concurs — nu îți rescrii propria sortare cu bucle imbricate, ci folosești unealta gata făcută din bibliotecă: rapidă, corectă și greu de stricat.
Intuiția
Ai văzut deja sortarea pătratică (compari perechi vecine, în n² pași) și căutarea
binară (înjumătățești de fiecare dată intervalul). Biblioteca standard C++ (STL)
îți oferă exact aceste idei, dar implementate optim: std::sort ordonează în
O(n log n), iar std::lower_bound și std::binary_search caută într-un șir
deja sortat în O(log n). Tu spui ce vrei; unealta știe cum.
Cele două unelte merg mână în mână: întâi std::sort aduce șirul în ordine
crescătoare în O(n log n), abia apoi căutările binare (lower_bound,
upper_bound, binary_search) pot lucra pe acel range sortat în O(log n).
Fără sortare prealabilă, căutarea binară dă răspunsuri greșite — taie jumătăți
dintr-un șir care nu respectă ordinea pe care o presupune.