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