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
