Despre algoritmi si structuri de date
Stefanescu Mihai
  • Keymaster
  • 54 Posts
Facebook account Twitter account Google plus account LinkedIn account

Am observat ca sunt foarte multi programatori care se blocheaza cand ajungem sa discutam despre algoritmi si m-am gandit sa deschid acest topic sa clarificam putin chestiile care nu va sunt clare.</p>

Am sa incep sa detaliez cativa algoritmi uzuali si daca aveti intrebari va astept.</p>

Stefanescu Mihai
  • Keymaster
  • 54 Posts
Facebook account Twitter account Google plus account LinkedIn account

Cautarea liniara.
Acesta este un algoritm foarte simplu. Aici discutam despre o cautare secventiala pe toate elementele luate unul cate unul. 
Hai sa presupunem ca avem urmatoarele date (nu conteaza cum sunt stocate, putem presupune ca avem de a face cu un vector):

[7, 12, 18, 21, 27, 30, 32, 34, 48, 52]


Algoritm


Avem Array-ul A si valoarea cautata X
Pas 1: Avem i = 1
Pas 2: Daca i > n mergem la pasul 7
Pas 3: Daca A[i] == x mergem la pasul 6
Pas 4: Setam i = i + 1
Pas 5: Mergi la pasul 2
Pas 6: Afiseaza elementul x gasit la indexul i si mergi la pasul 8
Pas 7: Afiseaza un mesaj ca nu am gasit elementul
Pas 8: Iesi din program

    int A[10] = {7, 12, 18, 21, 27, 30, 32, 34, 48, 52};
    int searched = 27;

    for(int i = 1; i<10; i++){
        if(A[i] == searched){
            cout << "Am gasit elementul: " << A[i] << " la pozitia " << i;
        }
    }

 

Stefanescu Mihai
  • Keymaster
  • 54 Posts
Facebook account Twitter account Google plus account LinkedIn account

Cautarea binara este un algoritm de cautare rapid, cu o complexitate de 0(log n).
Acest algoritm de cautare functioneaza pe principiul divide et impera.
Ca acest algoritm sa functioneze corect datele trebuie sa fie sortate.

Algoritmul de Cautare binara se uita dupa un anumit element comparandul elementul din mijlocul colectiei. Daca se gaseste elementul dorit
este returnat index-ul colectiei. Daca elementul mijlociu din colectie este mai mare ca elementul cautat, atunci cautam in partea stanga 
a colectiei, altfel cautam in partea dreapta a colectiei.

Cum functioneaza?
Pentru a va fi cat mai simplu am sa incerc sa va explic cu un exemplu. Presupunem ca avem urmatorul array:

[7, 12, 17, 24, 29, 30, 33, 37, 41, 45]

In primul rand trebuie sa determinam elementul de mijloc al array-ului folosind formula:

mid = low + (high - low) / 2

Array-ul de mai sus are indecsii de la 0 la 9, astfel incat formula va deveni:

0 + (9 - 0)/2 = 4 (luam partea intreaga a lui 4.5).

Presupunem ca valoarea pe care o cautam este 30.

Acum, daca ne uitam care este valoarea de pe pozitia 4 bservam ca este 29, care nu se potriveste cu cautarea noastra, dar observam ca este mai mica decat valoarea
pe care o cautam, asa ca mergem in partea dreapta a array-ului.

Primul pas este sa cautam din nou valoarea de mijloc.

low = mid + 1
mid = low + (high - low) / 2

Noul nostru mid este 7, verificam valoarea de pe pozitia 7 si observam ca este 37, o valoare mai mare decat valoarea cautata de noi (30).

Acum luam array-ul din stanga, pentru ca valoarea cautata de noi este mai mica decat valoarea mid.

Acum ca am redus din nou array-ul si am ajuns la pozitia 5. Verificam daca valoarea de pe pozitia 5 este ceea ce cautam, intradevar este ceea ce cautam.

#include 
#include 

using namespace std;

int cautareBinara(int arr[], int l, int r, int x)
{
   if (r >= l)
   {
        int mid = l + (r - l)/2;
        if (arr[mid] == x)
            return mid;

        if (arr[mid] > x)
            return cautareBinara(arr, l, mid-1, x);

        return cautareBinara(arr, mid+1, r, x);
   }

   return -1;
}

int main()
{
   int arr[] = {7, 12, 17, 24, 29, 30, 33, 37, 41, 45};
   int n = sizeof(arr)/ sizeof(arr[0]);
   int x = 30;
   int result = cautareBinara(arr, 0, n-1, x);
   (result == -1)? printf("Elementul nu este prezent in array")
                 : printf("Elementul este prezent pe pozitia %d",
                                                   result);
   return 0;
}

Trebuie sa fii inregistrat sau autentificat pentru a posta!