Algoritmi de cautare in tablouri

Cautarea este operatia prin care se urmareste gasirea unui anumit element intr-o structura de date. In cazul tablourilor unidimensionale, metodele de cautare cele mai raspandite sunt cautarea secventiala si cautarea binara.

Amintim ca, in limbajul Java, daca elementele tabloului sunt obiecte, compararea acestora cu obiectul cautat se face folosind un comparator.

Cautarea secventiala

Se considera dat un tablou unidimensional si se cere sa se determine indicele componentei care are o valoare data. Cautarea secventiala in tablou decurge astfel: se porneste de la prima componenta a tabloului (de indice 0) si se compara cu valoarea cautata. Daca nu corespunde, se trece la componenta urmatoare si asa mai departe, pana cand se gaseste componenta cu valoarea cautata. Daca s-a gasit o astfel de componenta, se intoarce indicele corespunzator. In caz contrar, se intoarce un indice imposibil (de regula -1) sau se genereaza o exceptie.
 
Algoritmul cautarii binare este foarte simplu. Iata-l descris in pseudocod.

   Fie tab un tablou cu n componente; 
   Fie i un numar intreg;
   Fie val valoarea cautata in tablou;
   i=0; // se porneste de la indicele 0
   Cat timp ((i diferit de-1) si (tab[i] diferit de val)) {
    i=i+1; // se trece la elementul urmator
    if(i>n) i=-1; // s-a depasit numarul de componente din tablou
   }
   intoarce i;

Se observa ca ciclul de cautare se incheie in urmatoarele doua situatii: cand s-a gasit o componenta tab[i] a tabloului egala cu valoarea cautata val, sau cand s-a depasit lungimea tabloului si s-a pus indicele i la valoarea -1.

Se observa ca in cazul cel mai defavorabil, cand valoarea cautata nu exista in tablou sau este plasata pe ultima pozitie, numarul de operatii simple este de ordinul n, deci complexitatea algoritmului de cautare secventiala in tablou este O(n).

In cazul tablourilor neordonate, cautarea secventiala este singura aplicabila.

Cautarea binara

In cazul tablourilor ordonate, este posibila aplicarea cautarii binare, care este mult mai rapida decat cea secventiala. Pentru a cauta o valoare val intr-un tablou ordonat, se procedeaza astfel: se compara valoarea val cu cea a componentei situata la mijlocul tabloului, fie acesta tab[k]. Daca valorile coincid, s-a gasit elementul cautat. Altfel, daca val<tab[k] se cauta valoarea in jumatatea din stanga a tabloului, iar daca val>tab[k] se cauta in jumatatea din dreapta. Se continua astfel, injumatatind mereu lungimea zonei de tablou in care se face cautarea. Procedura se opreste cand s-a gasit valoarea cautata, sau cand nu se mai poate face injumatatirea intervalului (acesta s-a redus la un singur element) si deci caloarea cautata nu exista in tablou.
 
Algoritmul cautarii binare poate fi scris in pseudocod astfel:

   Fie tab un tablou cu n componente;
   Fie i, j, k numere intregi;
   Fie val valoarea cautata in tablou;
   /* i si j sunt indicii componentelor de la capetele zonei de tablou in care se face cautarea */
   i=0; j=n; // se cauta initial in intregul tablou
   /* se determina indicele k al componentei de la mijlocul zonei de tablou dintre indicii i si j */
   k=(i+j)/2;
   /* Incepe ciclul de cautare */
   cat timp ((val diferit de tab[k]) si (i<=j)) {
     daca (val<tab[k])
       atunci j=k-1; // se cauta in jumatatea din stanga
       altfel i=k+1; // se cauta in jumatatea din dreapta
     k=(i+j)/2; // se determina noul mijloc al zonei de cautare
   }
   /* se verifica daca s-a gasit valoarea cautata */
   daca (val == tab[k]
     atunci intoarce k; // s-a gasit
     altfel intoarce -1; // nu s-a gasit

Pentru a stabili ordinul de marime al numarului de operatii elementare remarcam ca, daca numarul de componente ale tabloului este n, numarul de injumatatiri succesive ale zonei de cautare, dupa care lungimea acestei zone devine egala cu 1 este aproximativ log2n. Aceasta inseamna ca algoritmul de cautare binara are complexitatea O(log(n)). In consecinta, la valori mari ale lui n, cautarea binara este mult mai rapida decat cea secventiala.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati