Algoritmul de căutare binară este un algoritm de căutare folosit pentru a găsi un element într-o listă ordonată (tablou unidimensional/vector). Algoritmul funcţionează pe baza tehnicii divide et impera. Valoarea căutată este comparată cu cea a elementului din mijlocul listei. Dacă e egală cu cea a acelui element, algoritmul se termină. Dacă e mai mare decât acea valoare, algoritmul se reia, de la mijlocul listei până la sfârşit, iar dacă e mai mică, algoritmul se reia pentru elementele de la începutul listei până la mijloc.


Se citeşte un vector cu n componente numere întregi (numerele se presupun ordonate crescător) şi o valoare întreagă ("nr"). Să se decidă dacă nr se găseşte sau nu printre numerele citite, iar în caz afirmativ să se tipărească indicele componentei care conţine această valoare.



#include<iostream.h>

int v[100], n, nr;

void cautare_binara(int p, int u)

{

int m = (p+u)/2;

if (nr==v[m])

return 1;OneSearchGlass.jpg

else

if (p<u)

if (nr<v[m])

return cautare_binara(p, m-1);

else

return cautare_binara(m+1, u);

else

return 0;

}

int main (void)

{

cout<<”n=”; cin>>n;

for (int i=1; i<=n; i++)

{

cout<<”v[“<<i<<”]=”; cin>>v[i];

}

cout<<”nr=”; cin>>nr;

if(cautare_binara(0,n-1))

cout<<"da";

else

cout<<"nu";

return 0;

}



...inapoi