Algoritmi de căutare în tablouri

Căutarea este operația prin care se urmărește găsirea unui anumit element într-o structură de date. În cazul tablourilor unidimensionale, metodele de căutare cele mai răspândite sunt căutarea secvențială și căutarea binară.

Amintim că, în limbajul Java, dacă elementele tabloului sunt obiecte, pentru a fi comparate acestea trebuie să aparțină unei clase care implementează interfața comparable, sau compararea acestora cu obiectul căutat se face folosind un comparator.

Căutarea secvențială

Se consideră dat un tablou unidimensional și se cere să se determine indicele componentei care are o valoare dată. Căutarea secvențială în tablou decurge astfel: se pornește de la prima componentă a tabloului (de indice 0) și se compară cu valoarea căutată. Dacă nu corespunde, se trece la componenta urmatoare și așa mai departe, până când se găsește componenta cu valoarea căutată. Dacă s-a găsit o astfel de componentă, se întoarce indicele corespunzător. În caz contrar, se intoarce un indice imposibil (de regula -1) sau se genereaza o excepție.
 
Algoritmul căutarii binare este foarte simplu. Iată-l descris în pseudocod.

   Fie tab un tablou cu n componente; 
   Fie i un numar întreg;
   Fie val valoarea căutată în tablou;
   i=0; // se pornește de la indicele 0
   Cât timp ((i diferit de -1) și (tab[i] diferit de val)) {
    i=i+1; // se trece la elementul următor
    if(i>n) i=-1; // s-a depășit numarul de componente din tablou
   }
   intoarce i;

Se observă că ciclul de căutare se încheie în urmatoarele două situații: când s-a găsit o componentă tab[i] a tabloului egală cu valoarea căutată val, sau când s-a depășit lungimea tabloului și s-a pus indicele i la valoarea -1.

Se observă că în cazul cel mai defavorabil, când valoarea căutată nu există în tablou sau este plasată pe ultima poziție, numărul de operații simple este de ordinul n, deci complexitatea algoritmului de căutare secvențială în tablou este O(n).

În cazul tablourilor neordonate, căutarea secvențială este singura aplicabilă.

Căutarea binară

În cazul tablourilor ordonate, este posibilă aplicarea căutării binare, care este mult mai rapidă decat cea secvențială. Pentru a căuta o valoare val  într-un tablou ordonat, se procedează astfel: se compară valoarea val cu cea a componentei situate la mijlocul tabloului, fie acesta tab[k]. Dacă valorile coincid, s-a găsit elementul căutat. Altfel, dacă val<tab[k] se caută valoarea în jumatatea din stanga a tabloului, iar dacă val>tab[k] se caută în jumatatea din dreapta. Se continuă astfel, înjumătătind mereu lungimea zonei de tablou în care se face căutarea. Procedura se oprește când s-a găsit valoarea căutată, sau când nu se mai poate face înjumătățirea intervalului (acesta s-a redus la un singur element) si deci valoarea căutată nu există în tablou.
 
Algoritmul căutării binare poate fi scris în pseudocod astfel:

   Fie tab un tablou cu n componente;
   Fie i, j, k numere întregi;
   Fie val valoarea căutată în tablou;
   /* i si j sunt indicii componentelor de la capetele zonei de tablou în care se face căutarea */
   i=0; j=n; // se caută inițial în întregul 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 */
   cât timp ((val diferit de tab[k])și (i<=j)) {
     dacă (val<tab[k])
       atunci j=k-1; // se caută în jumatatea din stânga
       altfel i=k+1; // se caută în jumatatea din dreapta
     k=(i+j)/2; // se determină noul mijloc al zonei de căutare
   }
   /* se verifică dacă s-a găsit valoarea căutată */
   dacă (val == tab[k]
     atunci întoarce k; // s-a găsit
     altfel întoarce -1; // nu s-a găsit

Pentru a stabili ordinul de mărime al numărului de operații elementare remarcăm că, dacă numărul de componente ale tabloului este n, numărul de înjumătățiri succesive ale zonei de căutare, după care lungimea acestei zone devine egală cu 1, este aproximativ log2n. Aceasta înseamnă că algoritmul de căutare binară are complexitatea O(log(n)). În consecință, la valori mari ale lui n, căutarea binară este mult mai rapidă decât cea secvențială.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați