Căutarea unui element

Căutarea secvențială

  Căutarea secvențială este căutarea într-un șir neordonat ce presupune parcurgerea șirului element cu element, verificând de fiecare dată dacă este cel căutat, sau are proprietatea dorită.

int n, v[1001], x;
...
for(int i=0; i<n; i++)
  if(v[i]==x) cout<<i<<' ';

  Se parcurge tabloul cu o structură for și la fiecare pas verificăm egalitatea elemtnului cu variabila x. Când găsim un element bun, afișăm poziția în care l-am găsit și continuăm căutarea.
  Acest algortim este un exemplu, instrucțiunile din for se pot modifica după cerințele problemei.


Căutare binară

  Căutarea binară se realizează într-un șir ordonat și constă în înjumătățirea repetată a șirului și redirecționarea spre jumătatea potrivită.

int n, v[1001], x;
...
unsigned c1=0, c2=n-1, m;
while(c1<=c2){
  m=(c1+c2)/2;
  if(x==v[m]) cout<<m; break;
  else
    if (x<v[m]) c2=m-1;
    else c1=m+1;
}

  Inițial, capetele vor fi limitele șirului, iar mijlocul m va deveni poziția din mijlocul celor două capete. Când m este chiar poziția pe care o căutăm, afișăm și ieșim din structuri. Dacă nu, vom actualiza unul din capete în funcție de pozția elementului căutat. Dacă ceea ce căutăm este mai mic decât mijocul, capătul al doilea (c2) va deveni mijlocul curent, pentru a relua căutarea în prima jumătate (analog cu capătul 1 dacă valoarea este mai mare decât mijlocul).