Cautarea unui element intr-un vector

In urmatorul articol vom prezenta cele 2 tipuri de cautare ale unui element intr-un vecor.

1) Cautarea Secventiala

Acest algoritm cauta elementul succesiv in componentele vectorului. Un caz practic ar fi exemplul cautarii unui nume in cartea de telefon. Deschidem cartea la intamplare,dorim sa cautam numele „Popa Andrei „. Verificam daca numele se afla in prima partea a cartii sau in a doua parte. Continuam cautarea in portiunea respectiva, actiunea se repeta pana la gasirea numelui.

La fel este si in cazul numerelor dintr-un vector.

#include <iostream>

int main()
{
    int n,v[100],i,gasit=0,x;
    cout<<"Dati n : ";cin>>n;
    cout<<"Dati nr pe care trebuie sa-l cautam: ";cin>>x;
    for (i=0;i<n;i++)
    {
         cout<<"v["<<i+1<<"]=";cin>>v[i];
    }
    i=1;
    while ( (i<=n) && (!gasit) )
   {
       if (v[i]==x) gasit=1;
       i++;
   }
   if (gasit) cout<<x<<" se afla in vector";
   else cout<<x<<" nu se afla in vector";

   return 0;
}

Cautarea secventiala se poate face intr-un vector cu elementele neordonate.Astfel complexitatea algoritmului este liniara : O(n).

2) Cautarea Binara

Cautarea binara se bazeaza pe tehnica de programare Divide et Impera. Elementul cautat este „verificat” cu mijlocul vectorului. Daca elementul este egal cu mijlocul,cautarea se termina. Insa daca nu sunt egale, se compara valoarea mijlocului cu cea a elementului de cautat. Daca elementul este mai mare se continua cautarea de la mijlocul listei pana la sfarsit, iar daca este mai mic se continua cautarea de la inceput pana la mijloc.

#include <iostream.h>

int main()
{
    int mij,n=7,i,x=10,v[7]={4,5,8,10,20,45,76},st,dr,g=0;
    st=0;
    dr=n-1;
    mij=(st+dr)/2;
    while  ( (st<dr) && (!g) )
    {
         if (v[mij]==x) {g=1;break;}
         else if (v[mij]<x) st=mij+1;
         else if (v[mij]>x) dr=mij-1;
    }
    if (g) cout<<x<<" se afla in vector pe pozitia "<<mij;
    else cout<<x<<" nu se afla in vector";

    return 0;
}

De aceasta data am dat elementele vectorului si numarul cautat, nu le-am mai citit. Observam ca am folosit o tehnica numita divide si cucereste. Dupa cum bine stim de la clasicul QuickSort orice algoritm divide si cucereste are timp logaritmic. 🙂