Informatică Programare
Exercitii rezolvate cu cautare binara in C++
Căutarea binară este un algoritm eficient pentru găsirea unui element într-un vector sortat. Funcționează prin împărțirea repetată a intervalului de căutare la jumătate. Vom rezolva două exerciții tipice în C++.
Exercițiul 1: Găsirea poziției unui element
- 1 Pasul 1: Inițializare Declarăm un vector sortat, de exemplu: int v[] = {1, 3, 5, 7, 9}; și elementul căutat x = 5.
- 2 Pasul 2: Algoritmul binar Setăm stânga = 0, dreapta = 4 (lungime-1). Cât timp stânga <= dreapta, calculăm mijloc = (stânga + dreapta) / 2.
- 3 Pasul 3: Comparație și ajustare Dacă v[mijloc] == x, returnăm mijloc. Dacă v[mijloc] < x, stânga = mijloc + 1, altfel dreapta = mijloc - 1.
- 4 Pasul 4: Rezultat Pentru x=5, algoritmul găsește la mijloc=2, returnând poziția 2 (indexare de la 0).
Exercițiul 2: Numărul de apariții
- 1 Pasul 1: Găsirea primei apariții Folosim căutarea binară modificată: dacă v[mijloc] >= x, dreapta = mijloc - 1, altfel stânga = mijloc + 1.
- 2 Pasul 2: Găsirea ultimei apariții Modificăm: dacă v[mijloc] <= x, stânga = mijloc + 1, altfel dreapta = mijloc - 1.
- 3 Pasul 3: Calcul final Pentru vectorul {2, 2, 2, 4, 5} și x=2, prima apariție e la 0, ultima la 2, deci sunt 3 apariții.
Verifică mereu că vectorul este sortat înainte de a aplica căutarea binară.