Algoritm recursiv pentru căutare binară (clasa a X-a)
Am învățat în clasa a IX-a despre algoritmul de Căutare binară (mai multe detalii aici). Algoritmul caută într-un mod eficient dacă un element există sau nu într-un șir ordonat crescător, reducând la fiecare pas câte jumătate din elementele șirului rămas.
În această lecție vom discuta despre o implementare recursivă a algoritmului în C++, foarte ușor de înțeles.
Ce este căutarea binară?
Căutarea binară este un algoritm care caută un element într-un șir de valori ordonate (de regulă, crescător). Căutarea se face prin următorul algoritm. Cât timp mai avem elemente:
- Luăm numărul din mijlocul secvenței curente;
- Dacă este egal cu numărul căutat, am găsit numărul și ne oprim;
- Dacă este mai mare decât numărul căutat, atunci automat toate numerele din dreapta elementului din mijlocul șirului vor fi și ele mai mari decât numărul căutat, deci nu trebuie să le mai verificăm și putem reduce șirul în jumătate (luând prima parte);
- Similar, dacă este mai mic decât numărul căutat, luăm a doua jumătate.
Un exemplu concret se găsește la lecția pentru clasa a IX-a, împreună cu grafice.
Înțelegerea algoritmului recursiv
Algoritmul recursiv se bazează pe o funcție (un subprogram). Acest subprogram este recursiv, adică îl vom apela pe el însuși în cadrul său.
Funcția va avea patru parametri: a[]
, un vector de numere întregi (sau de
orice alt tip, în funcție de cerință), împreună cu doi indici st
și dr
,
care marchează pozițiile de început și de final a secvenței curente în care
căutăm elementul nostru, precum și valoarea de căutat: x
.
Funcția returnează 1
, dacă elementul x
a fost găsit, respectiv 0
în caz
contrar.
Practic, după ce apelăm cautBin(a, 1, n, x)
, ne așteptăm să primim 1
sau
0
în funcție de existența lui x
în a
.
Funcția va face următoarele:
- Dacă secvența noastră nu este validă (adică
st
este mai mare strict decâtdr
), atunci ne oprim; - Dacă secvența noastră este de un singur element (
st
șidr
sunt egale), atunci returnăm1
dacă acest element este egal cux
, sau0
în caz contrar; - În caz contrar, dacă secvența noastră are cel puțin două elemente, luăm elementul din mijloc și îl comparăm cu
x
. În funcție de această comparație, fie returnăm1
(dacă mijlocul este chiar egal cux
), fie returnămcautBin(a, st, mij - 1, x)
, saucautBin(a, mij + 1, dr, x)
, după caz (dacă mijlocul este mai mare sau mai mic decâtx
).
Implementare în C++
Mai jos implementăm căutarea binară în C++ recursiv.
#include <iostream>
using namespace std;
int cautBin(int a[], int st, int dr, int x) {
//Explicații: infoas.ro
if(st > dr) return 0;
if(st == dr) {
if(a[st] == x) return 1;
else return 0;
}
int mij = (st + dr) / 2;
if(a[mij] == x) return 1;
else if(a[mij] < x) return cautBin(a, mij + 1, dr, x);
else return cautBin(a, st, mij - 1, x);
}
int main()
{
//Declarăm și citim datele în ordinea: lungimea șirului, elementele șirului și valoarea de căutat
int a[100], n, x;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> x;
//Căutăm binar
if(cautBin(a, 1, n, x) == 1) {
cout << "Am gasit valoarea " << x << " in sir!";
} else {
cout << "Nu am gasit valoarea " << x << " in sir :(";
}
return 0;
}
Alte resurse sau bibliografie
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Comentarii 0