Informatică Programare
Algoritm cautare binara C++
Căutarea binară este un algoritm rapid pentru găsirea unui element într-un vector sortat. Funcționează prin împărțirea repetată a intervalului de căutare la jumătate. Are complexitate O(log n), mult mai bună decât căutarea liniară.
Pașii algoritmului
- 1 Stabilirea intervalului Se definește stânga = 0 și dreapta = n-1, unde n este lungimea vectorului.
- 2 Calcularea mijlocului Mijloc = (stânga + dreapta) / 2.
- 3 Compararea elementului Dacă v[mijloc] == x, elementul a fost găsit. Altfel, ajustează stânga sau dreapta.
Exemplu numeric
- Vectorul inițial v = {1, 3, 5, 7, 9}, n = 5, căutăm x = 7.
- Prima iterație stânga=0, dreapta=4, mijloc=2, v[2]=5 < 7, deci stânga devine 3.
- A doua iterație stânga=3, dreapta=4, mijloc=3, v[3]=7, element găsit.
Verifică întotdeauna că vectorul este sortat înainte de a aplica căutarea binară.