Algoritmi de cautare

O sa consideram cazul in care cautam un numar intreg intr-o colectie(vector) de numere intregi.

1. Cautare secventiala. Este cea mai simpla metoda, se parcurge vectorul de la primul la ultimul element si se compara pe rand elementul cautat cu fiecare element al vectorului.

int v[100], n, a, pos=-1;
//se citeste n si apoi se citesc n numere intregi in vectorul v.
//a este valoarea pe care o cautam si pos este pozitia in vector
// la care am gasit valoarea a
for (int i = 0; i < n; i++)
{
    if (v[i] == a)  
    {
        pos = i;
        break;
    }
}
if (pos >= 0)
{
    cout<<"valoarea cautata a fost gasita pe pozitia "<<pos;
}
else
{
    cout<<"valoarea cautata nu a fost gasita";
}

2. Cautare secventiala intr-un vector sortat crescator. Este acelasi algoritm de mai sus cu deosebirea ca vectorul in care cautam este ordonat crescator. Aici se poate face o mica modificare pentru ca algoritmul sa devina mai eficient. Daca ajungem la o valoare in vector mai mare decat valoarea cautata abandonam cautarea deoarece toate valorile din vector care vor urma sunt mai mari decat elementul curent.

int v[100], n, a, pos=-1;
//se citeste n si apoi se citesc n numere intregi ordonate crescator
//in vectorul v. a este valoarea pe care o cautam si pos este 
//pozitia in vector la care am gasit valoarea a
for (int i = 0; i < n; i++)
{
    if (v[i] == a)  
    {
        pos = i;
        break;
    }
    else if (v[i] > a)
    {
        break;
    }
}
if (pos >= 0)
{
    cout<<"valoarea cautata a fost gasita pe pozitia "<<pos;
}
else
{
    cout<<"valoarea cautata nu a fost gasita";
}

3. Cautare binara. Vectorul in care cautam este ordonat crescator. Folosim metoda de programare "Divide et impera" si o functie recursiva. Comparam valoarea cautata cu elementul din mijlocul vectorului si daca este egalitate terminam cautarea. Daca valoarea cautata este mai mica decat elementul din mijlocul vectorului atunci continuam cautarea in jumatatea stanga a vectorului (de la primul element pana la elementul din stanga elementului din mijloc) si daca este mai mare continuam cautarea in jumatatea dreapta. Conditia de oprire a recursivitatii este daca secventa in care cautam este vida sau daca contine un singur element caz in care comparam acest element cu valoarea cautata.

//intoarce -1 daca nu a fost gasita valoarea si indexul din vector 
//daca valoarea a fost gasita
int cauta_binar(int v[], int start, int sfarsit, int a)
{
    if (start > sfarsit)
    {
        return -1;
    }
    if (start == sfarsit)
    {
        return (a==v[start])?start:-1;
    }
    int mijloc = (start+sfarsit)/2;
    if (a == v[mijloc])
    {
        return mijloc;
    }
    else if (a < v[mijloc])
    {
        return cauta_binar(v, start, mijloc-1, a);
    }
    else
    {
        return cauta_binar(v, mijloc+1, sfarsit, a);
    }
}

Daca avem un vector de numere intregi ordonate crescator si vrem sa cautam o valoare intreaga "a" putem face asa:

int v[100], n, a;
//citim n, cele n valori si valoarea de cautat a
int idx = cauta_binar(v, 0, n-1, a);
if (idx >= 0)
{
    cout<<"am gasit valoarea cautata pe pozitia "<<idx;
}
else
{
    cout<<"nu s-a gasit valoarea cautata";
}