De ce contează?
La concurs n-ai timp să rescrii sortarea sau căutarea binară de fiecare dată. Biblioteca standard (STL) ți le oferă gata făcute, testate și rapide. E ca diferența dintre a-ți face singur uneltele și a folosi o trusă profesională.
std::sort — sortarea de bază
Sortează un interval în O(n log n). Implicit crescător; cu un comparator, după orice criteriu.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int v[] = {5, 3, 8, 1, 9};
int n = 5;
sort(v, v + n); // crescator: 1 3 5 8 9
sort(v, v + n, greater<int>()); // descrescator: 9 8 5 3 1
for (int i = 0; i < n; i++) cout << v[i] << " ";
return 0;
}sort(v, v + n) primește începutul și sfârșitul (poziția de după ultimul element).
La concurs înlocuiește orice sortare pătratică — e O(n log n) și deja optimizată.
Căutare pe vector sortat
Toate trei funcțiile cer un vector sortat (folosesc căutare binară):
| Funcție | Ce returnează |
|---|---|
binary_search(v, v+n, x) | true/false: există x? |
lower_bound(v, v+n, x) | iterator spre primul element ≥ x |
upper_bound(v, v+n, x) | iterator spre primul element > x |
int v[] = {1, 3, 3, 3, 5, 8}; // sortat
int n = 6;
bool exista = binary_search(v, v + n, 3); // true
int pozJos = lower_bound(v, v + n, 3) - v; // 1 (primul 3)
int pozSus = upper_bound(v, v + n, 3) - v; // 4 (primul dupa 3)
int cate = pozSus - pozJos; // 3 -> de cate ori apare 3Scăzând v din iterator obții indicele. Diferența upper_bound − lower_bound dă
numărul de apariții ale unei valori — un truc folosit des pentru frecvențe pe vector sortat.
Cu structuri și comparatori
sort merge și pe vectori de structuri, cu un comparator (vezi lecția de sortare a
structurilor). lower_bound/upper_bound acceptă și ele un comparator, dar trebuie să fie
același criteriu după care e sortat vectorul.
Complexitate
| Operație | Timp |
|---|---|
sort | O(n log n) |
binary_search / lower_bound / upper_bound | O(log n) |
Capcane reale la STL sortare/căutare:
- Cauți binar pe vector nesortat: rezultate nedefinite. Sortează întâi.
- Confuzi
lower_boundcuupper_bound: unul dă primul ≥ x, celălalt primul > x. La numărarea aparițiilor, ai nevoie de ambele. - Uiți
- vpentru indice: funcțiile returnează un iterator (pointer), nu un index direct. Scazi începutul vectorului. - Comparator inconsistent cu sortarea: dacă vectorul e sortat după un criteriu, dar cauți cu altul, căutarea binară dă rezultate greșite.
De reținut
sort(v, v+n[, cmp])— O(n log n), prima alegere la sortare.- Pe vector sortat:
binary_search(există?),lower_bound(primul ≥ x),upper_bound(primul > x). - Scazi
vdin iterator pentru indice;upper − lower= numărul de apariții.