O data ce ai inceput sa utilizezi structuri de date in Java, in mod inevitabil vei intalni situatii in care vei fi nevoit sa le sortezi sau sa cauti ceva anume. In cazul acestui tutorial Java pentru incepatori, vom utiliza array-uri pentru a ilustra cativa algoritmi de baza pentru sortare, cautare si recursivitate.
Un algoritm este o procedura, o serie de pasi pe care ii definesti pentru a rezolva o anumita problema.
Recursivitate
Anumite tehnici pe care le vom utiliza se bazeaza pe procesele recursive, asadar sa le studiem mai intai pe acestea. O metoda recursiva este de fapt o functie care se apeleaza pe ea insasi. Utilizarea metodelor recursive in mod eficient necesita ceva practica, deoarece programul poate fi prins cu usurinta intr-o bucla infinita.
Pentru a observa cum actioneaza o functie recursiva, sa cream un exemplu banal. Creeaza un nou proiect Java si scrie urmatorul cod in clasa principala, dupa metoda main:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
<span class="hl-comment">//</span><span class="hl-comment"> metoda recursiva</span> <span class="hl-reserved">public</span> static int <span class="hl-identifier">doSomething</span><span class="hl-brackets">(</span>int <span class="hl-identifier">someNumber</span><span class="hl-brackets">)</span> <span class="hl-brackets">{</span> <span class="hl-comment">//</span><span class="hl-comment"> verifica valoarea parametrului</span> <span class="hl-reserved">if</span><span class="hl-brackets">(</span><span class="hl-identifier">someNumber</span><span class="hl-code"><=</span><span class="hl-number">0</span><span class="hl-brackets">)</span> <span class="hl-reserved">return</span> <span class="hl-identifier">someNumber</span><span class="hl-code">; </span><span class="hl-reserved">else</span> <span class="hl-brackets">{</span> <span class="hl-comment">//</span><span class="hl-comment"> decrementeaza valoarea si apeleaza din nou functia</span> <span class="hl-identifier">someNumber</span><span class="hl-code">--; </span><span class="hl-identifier">System</span><span class="hl-code">.</span><span class="hl-identifier">out</span><span class="hl-code">.</span><span class="hl-identifier">println</span><span class="hl-brackets">(</span><span class="hl-identifier">someNumber</span><span class="hl-brackets">)</span><span class="hl-code">; </span><span class="hl-reserved">return</span><span class="hl-brackets">(</span><span class="hl-identifier">doSomething</span><span class="hl-brackets">(</span><span class="hl-identifier">someNumber</span><span class="hl-brackets">)</span><span class="hl-brackets">)</span><span class="hl-code">; </span><span class="hl-brackets">}</span> <span class="hl-brackets">}</span> |
Acum apeleaza noua functie din metoda main.
1 2 |
int <span class="hl-identifier">result</span><span class="hl-code"> = </span><span class="hl-identifier">doSomething</span><span class="hl-brackets">(</span><span class="hl-number">10</span><span class="hl-brackets">)</span><span class="hl-code">; </span><span class="hl-identifier">System</span><span class="hl-code">.</span><span class="hl-identifier">out</span><span class="hl-code">.</span><span class="hl-identifier">println</span><span class="hl-brackets">(</span><span class="hl-quotes">"</span><span class="hl-string">rezultat: </span><span class="hl-quotes">"</span><span class="hl-code"> + </span><span class="hl-identifier">result</span><span class="hl-brackets">)</span><span class="hl-code">;</span> |
Programul va numara de la valoarea int introdusa catre zero. Experimenteaza schimband valoarea parametrului int introdus in metoda si observa ce efecte are asupra rezultatului afisat pe consola. Metoda reuseste sa evite blocarea intr-o bucla (cauzata de solicitarea repetata a acesteia) utilizand o instructiune conditionala �if’.
Aceasta metoda simpla are un efect similar unei bucle, dar dupa cum vei observa, recursivitatea poate fi utila mai ales daca ai o problema complexa care este rezolvata cel mai bine in etape, fiecare etapa aducandu-te cu un pas mai aproape de solutie prin simplificare. Un ingredient necesar al metodelor recursive il reprezinta deci precizarea explicita a modului in care metodele ar trebui sa se comporte pentru cel mai banal input, si apoi cu fiecare iteratie, te indrepti catre acest caz foarte simplu. In exemplul de mai sus, cazul cel mai simplu este atunci cand parametrul int este mai mic sau egal cu zero.
Incearca sa nu te ingrijorezi daca aceasta pare a fi la inceput o practica ciudata, de indata ce incepi sa utilizezi metode de sortare, abordarea recursiva va deveni mai clara.
Sortarea
Motivul principal pentru pastrarea unei colectii de date intr-o ordine sortata il reprezinta usurinta cu care se gasesc articolele in cadrul acesteia. Cu toate acestea, pastrarea datelor intr-o ordine sortata implica o anumita munca de procesare, mai ales la adaugarea sau indepartarea articolelor.
Cand spunem, de exemplu, ca un array este sortat, intelegem ca elementele acestuia sunt aranjate intr-o anumita ordine. Uneori, regula de ordonare este intuitiva: de exemplu daca array-ul contine numere, ele vor fi ordonate crescator (sau descrescator) dupa valoarea lor. In mod similar, daca array-ul contine siruri de caractere, ele pot fi sortate alfabetic.
Oricum, exista situatii in care regula de sortare este mai putin clara – imagineaza-ti ca ti-ai creat o clasa proprie, si ca doresti sa stochezi obiecte de tipul respectiv intr-un array. Va trebui sa decizi apoi care este regula de sortare pentru aceste obiecte. Pentru aceasta trebuie sa te gandesti la modul de comparare a doua obiecte din aceeasi clasa. Cand compari doua obiecte ale clasei, exista situatia in care, fie unul este „mai mare” decat celalalt, fie sunt „egale”. Pentru a putea ordona obiectele astfel, clasa ta trebuie sa implementeze interfata Comparable, incluzand o definitie pentru metoda compareTo. In cadrul acestei metode va trebui sa definesti regula de sortare pentru obiectele din clasa, de exemplu, ai putea utiliza valoarea unor proprietati ale clasei pentru a decide care obiect este „mai mare”.
Nota: Ai grija atunci cand utilizezi metoda equals deoarece in mod implicit ea este mostenita din clasa Object si lucreaza cu referintele obiectelor – de ex., testeaza daca numele a doua variabile indica acelasi obiect. Daca intentionezi sa utilizezi medoda equals, cel mai bine ar fi sa lucrezi cu propria implementare a acesteia, rescriind metoda implicita.
In cadrul acestui tutorial Java, vom ramane la tipuri de date simple pentru a ilustra cativa algoritmi de selectie.
Sortarea prin selectie
Sortarea prin selectie actioneaza prin descoperirea in permanenta a celui mai mic articol din colectie si prin plasarea acestuia la inceput. Creeaza un nou program si introdu urmatorul cod in metoda main pentru a crea un array continand cateva date ales in mod arbitrar:
1 2 |
<span class="hl-comment">//</span><span class="hl-comment">array cu date nesortate</span> int <span class="hl-brackets">[</span><span class="hl-brackets">]</span> <span class="hl-identifier">myData</span><span class="hl-code"> = </span><span class="hl-brackets">{</span><span class="hl-number">3</span><span class="hl-code">, </span><span class="hl-number">1</span><span class="hl-code">, </span><span class="hl-number">9</span><span class="hl-code">, </span><span class="hl-number">5</span><span class="hl-code">, </span><span class="hl-number">7</span><span class="hl-brackets">}</span><span class="hl-code">;</span> |
In continuare, vom utiliza sortarea prin selectie pentru a aranja elementele din array in ordine crescatoare. Algoritmul functioneaza astfel:
- In cadrul colectiei de date care urmeaza a fi sortate (initial, intreaga structura), gaseste cel mai mic articol;
- Plaseaza acest articol in prima pozitie (a structurii nesortate), inlocuind orice element care se afla deja acolo si muta elementul inlocuit la pozitia celui mai mic articol;
- Sectiunea nesortata contine acum un element mai putin (articolul tocmai considerat a fi cel mai mic si prin urmare, mutat);
- Continua plasarea celui mai mic element nesortat in prima pozitie pana cand toate datele au fost sortate.
Introdu urmatorul cod dupa declararea array-ului si compileaza programul, observand rezultatul:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
<span class="hl-comment">//</span><span class="hl-comment">parcurge array-ul intr-o bucla for</span> <span class="hl-reserved">for</span><span class="hl-brackets">(</span>int <span class="hl-identifier">pos</span><span class="hl-code">=</span><span class="hl-number">0</span><span class="hl-code">; </span><span class="hl-identifier">pos</span><span class="hl-code"> < </span><span class="hl-identifier">myData</span><span class="hl-code">.</span><span class="hl-identifier">length</span><span class="hl-code">-</span><span class="hl-number">1</span><span class="hl-code">; </span><span class="hl-identifier">pos</span><span class="hl-code">++</span><span class="hl-brackets">)</span> <span class="hl-brackets">{</span> <span class="hl-comment">/*</span><span class="hl-comment"> gaseste si retine pozitia * celui mai mic element * incepe de la pos si cauta in restul array-ului * (pos indica inceputul sectiunii nesortate) </span><span class="hl-comment">*/</span> int <span class="hl-identifier">minIndex</span><span class="hl-code"> = </span><span class="hl-identifier">pos</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment"> parcurge sectiunea nesortata</span> <span class="hl-reserved">for</span><span class="hl-brackets">(</span>int <span class="hl-identifier">next</span><span class="hl-code">=</span><span class="hl-identifier">pos</span><span class="hl-code">+</span><span class="hl-number">1</span><span class="hl-code">; </span><span class="hl-identifier">next</span><span class="hl-code">< </span><span class="hl-identifier">myData</span><span class="hl-code">.</span><span class="hl-identifier">length</span><span class="hl-code">; </span><span class="hl-identifier">next</span><span class="hl-code">++</span><span class="hl-brackets">)</span> <span class="hl-brackets">{</span> <span class="hl-reserved">if</span><span class="hl-brackets">(</span><span class="hl-identifier">myData</span><span class="hl-brackets">[</span><span class="hl-identifier">minIndex</span><span class="hl-brackets">]</span><span class="hl-code">></span><span class="hl-identifier">myData</span><span class="hl-brackets">[</span><span class="hl-identifier">next</span><span class="hl-brackets">]</span><span class="hl-brackets">)</span> <span class="hl-identifier">minIndex</span><span class="hl-code">=</span><span class="hl-identifier">next</span><span class="hl-code">; </span><span class="hl-brackets">}</span> <span class="hl-comment">//</span><span class="hl-comment">inverseaza pozitia elementelor daca este necesar</span> <span class="hl-reserved">if</span><span class="hl-brackets">(</span><span class="hl-identifier">minIndex</span><span class="hl-code">!=</span><span class="hl-identifier">pos</span><span class="hl-brackets">)</span> <span class="hl-brackets">{</span> <span class="hl-comment">//</span><span class="hl-comment">retine elementul curent indicat de pos</span> int <span class="hl-identifier">temp</span><span class="hl-code"> = </span><span class="hl-identifier">myData</span><span class="hl-brackets">[</span><span class="hl-identifier">pos</span><span class="hl-brackets">]</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment">copiaza cel mai mic element la pozitia pos</span> <span class="hl-identifier">myData</span><span class="hl-brackets">[</span><span class="hl-identifier">pos</span><span class="hl-brackets">]</span><span class="hl-code"> = </span><span class="hl-identifier">myData</span><span class="hl-brackets">[</span><span class="hl-identifier">minIndex</span><span class="hl-brackets">]</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment">copiaza elementul inlocuit la pozitia minIndex</span> <span class="hl-identifier">myData</span><span class="hl-brackets">[</span><span class="hl-identifier">minIndex</span><span class="hl-brackets">]</span><span class="hl-code"> = </span><span class="hl-identifier">temp</span><span class="hl-code">; </span><span class="hl-brackets">}</span> <span class="hl-comment">//</span><span class="hl-comment">afiseaza array-ul sortat</span> <span class="hl-reserved">for</span><span class="hl-brackets">(</span>int <span class="hl-identifier">p</span><span class="hl-code"> : </span><span class="hl-identifier">myData</span><span class="hl-brackets">)</span> <span class="hl-brackets">{</span> <span class="hl-identifier">System</span><span class="hl-code">.</span><span class="hl-identifier">out</span><span class="hl-code">.</span><span class="hl-identifier">print</span><span class="hl-brackets">(</span><span class="hl-identifier">p</span><span class="hl-brackets">)</span><span class="hl-code">; </span><span class="hl-brackets">}</span> <span class="hl-identifier">System</span><span class="hl-code">.</span><span class="hl-identifier">out</span><span class="hl-code">.</span><span class="hl-identifier">println</span><span class="hl-brackets">(</span><span class="hl-brackets">)</span><span class="hl-code">; </span><span class="hl-brackets">}</span> |
Cand privesti rezultatul programului, incearca sa observi articolele care se inlocuiesc in fiecare etapa – experimenteaza schimband valorile (sau ordinea lor) din array.
Sortarea prin interclasare
O metoda mai eficienta de sortare a continutului unui array este sortarea prin interclasare, care utilizeaza un algoritm recursiv. Aceasta se bazeaza pe ideea ca unificarea a doua array-uri deja sortate este o problema mai simpla decat ordonarea tuturor datelor dintr-un array nesortat. Deci, algoritmul sorteaza un array prin divizarea sa continua in doua parti si sortarea fiecareia, unificand rezultatele intr-un array sortat.
Adauga urmatoarea metoda in clasa ta (dupa functia main):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
<span class="hl-comment">/*</span><span class="hl-comment"> Functia mergeSort sorteaza datele dintr-un array * -parametrii transmisi sunt array-ul cu datele ce trebuiesc sortate, * un array temporar (temp) utilizat la calcule * si doua valori intregi care indica inceputul si sfarsitul * sectiunii din array ce trebuie ordonata </span><span class="hl-comment">*/</span> <span class="hl-reserved">public</span> static void <span class="hl-identifier">mergeSort</span><span class="hl-brackets">(</span>int<span class="hl-brackets">[</span><span class="hl-brackets">]</span> <span class="hl-identifier">dataArray</span><span class="hl-code">, </span>int<span class="hl-brackets">[</span><span class="hl-brackets">]</span> <span class="hl-identifier">tempArray</span><span class="hl-code">, </span>int <span class="hl-identifier">start</span><span class="hl-code">, </span>int <span class="hl-identifier">end</span><span class="hl-brackets">)</span> <span class="hl-brackets">{</span> <span class="hl-comment">//</span><span class="hl-comment"> daca start = end, array-ul a fost sortat</span> <span class="hl-reserved">if</span><span class="hl-brackets">(</span><span class="hl-identifier">start</span><span class="hl-code">==</span><span class="hl-identifier">end</span><span class="hl-brackets">)</span> <span class="hl-reserved">return</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment"> altfel imparte array-ul in 2 sectiuni</span> <span class="hl-reserved">else</span> <span class="hl-brackets">{</span> <span class="hl-comment">//</span><span class="hl-comment">calculeaza centrul array-ului</span> int <span class="hl-identifier">center</span><span class="hl-code"> = </span><span class="hl-brackets">(</span><span class="hl-identifier">start</span><span class="hl-code">+</span><span class="hl-identifier">end</span><span class="hl-brackets">)</span><span class="hl-code">/</span><span class="hl-number">2</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment">apeleaza mergeSort pentru prima jumatate</span> <span class="hl-identifier">mergeSort</span><span class="hl-brackets">(</span><span class="hl-identifier">dataArray</span><span class="hl-code">, </span><span class="hl-identifier">tempArray</span><span class="hl-code">, </span><span class="hl-identifier">start</span><span class="hl-code">, </span><span class="hl-identifier">center</span><span class="hl-brackets">)</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment">apeleaza mergeSort pentru cea de-a doua jumatate</span> <span class="hl-identifier">mergeSort</span><span class="hl-brackets">(</span><span class="hl-identifier">dataArray</span><span class="hl-code">, </span><span class="hl-identifier">tempArray</span><span class="hl-code">, </span><span class="hl-identifier">center</span><span class="hl-code">+</span><span class="hl-number">1</span><span class="hl-code">, </span><span class="hl-identifier">end</span><span class="hl-brackets">)</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment">uneste jumatatile intr-un singur array</span> int <span class="hl-identifier">firstIndex</span><span class="hl-code"> = </span><span class="hl-identifier">start</span><span class="hl-code">; </span>int <span class="hl-identifier">secondIndex</span><span class="hl-code"> = </span><span class="hl-identifier">center</span><span class="hl-code">+</span><span class="hl-number">1</span><span class="hl-code">; </span>int <span class="hl-identifier">thirdIndex</span><span class="hl-code"> = </span><span class="hl-identifier">start</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment">parcurge ambele parti</span> <span class="hl-reserved">while</span><span class="hl-brackets">(</span><span class="hl-identifier">thirdIndex</span><span class="hl-code"><=</span><span class="hl-identifier">end</span><span class="hl-brackets">)</span> <span class="hl-brackets">{</span> <span class="hl-comment">/*</span><span class="hl-comment"> parcurge partile * inserand cel mai mic element * in array-ul temp </span><span class="hl-comment">*/</span> <span class="hl-reserved">if</span><span class="hl-brackets">(</span><span class="hl-identifier">secondIndex</span><span class="hl-code">></span><span class="hl-identifier">end</span><span class="hl-code"> || </span><span class="hl-brackets">(</span><span class="hl-identifier">firstIndex</span><span class="hl-code"><=</span><span class="hl-identifier">center</span><span class="hl-code"> && </span><span class="hl-identifier">dataArray</span><span class="hl-brackets">[</span><span class="hl-identifier">firstIndex</span><span class="hl-brackets">]</span><span class="hl-code"><=</span><span class="hl-identifier">dataArray</span><span class="hl-brackets">[</span><span class="hl-identifier">secondIndex</span><span class="hl-brackets">]</span><span class="hl-brackets">)</span><span class="hl-brackets">)</span> <span class="hl-brackets">{</span> <span class="hl-identifier">tempArray</span><span class="hl-brackets">[</span><span class="hl-identifier">thirdIndex</span><span class="hl-brackets">]</span><span class="hl-code">=</span><span class="hl-identifier">dataArray</span><span class="hl-brackets">[</span><span class="hl-identifier">firstIndex</span><span class="hl-brackets">]</span><span class="hl-code">; </span><span class="hl-identifier">thirdIndex</span><span class="hl-code">++; </span><span class="hl-identifier">firstIndex</span><span class="hl-code">++; </span><span class="hl-brackets">}</span> <span class="hl-reserved">else</span> <span class="hl-brackets">{</span> <span class="hl-identifier">tempArray</span><span class="hl-brackets">[</span><span class="hl-identifier">thirdIndex</span><span class="hl-brackets">]</span><span class="hl-code">=</span><span class="hl-identifier">dataArray</span><span class="hl-brackets">[</span><span class="hl-identifier">secondIndex</span><span class="hl-brackets">]</span><span class="hl-code">; </span><span class="hl-identifier">thirdIndex</span><span class="hl-code">++; </span><span class="hl-identifier">secondIndex</span><span class="hl-code">++; </span><span class="hl-brackets">}</span> <span class="hl-brackets">}</span> <span class="hl-comment">//</span><span class="hl-comment">copiaza continutul array-ului temp in array-ul principal</span> <span class="hl-reserved">for</span><span class="hl-brackets">(</span>int <span class="hl-identifier">i</span><span class="hl-code">=</span><span class="hl-identifier">start</span><span class="hl-code">; </span><span class="hl-identifier">i</span><span class="hl-code"><=</span><span class="hl-identifier">end</span><span class="hl-code">; </span><span class="hl-identifier">i</span><span class="hl-code">++</span><span class="hl-brackets">)</span> <span class="hl-identifier">dataArray</span><span class="hl-brackets">[</span><span class="hl-identifier">i</span><span class="hl-brackets">]</span><span class="hl-code">=</span><span class="hl-identifier">tempArray</span><span class="hl-brackets">[</span><span class="hl-identifier">i</span><span class="hl-brackets">]</span><span class="hl-code">; </span><span class="hl-brackets">}</span> |
De fiecare data cand metoda ajunge la punctul de unificare a celor jumatati, fiecare jumatate a fost deja sortata, deoarece functia a fost aplicata mai intai asupra acestora. Asadar, metoda rezolva problema prin impartirea si simplificarea sa repetata. Acum, apeleaza noua metoda din main:
1 2 3 4 5 6 7 8 9 10 |
<span class="hl-comment">//</span><span class="hl-comment">array-ul ce trebuie ordonat</span> int<span class="hl-brackets">[</span><span class="hl-brackets">]</span> <span class="hl-identifier">someData</span><span class="hl-code"> = </span><span class="hl-brackets">{</span><span class="hl-number">4</span><span class="hl-code">, </span><span class="hl-number">3</span><span class="hl-code">, </span><span class="hl-number">7</span><span class="hl-code">, </span><span class="hl-number">6</span><span class="hl-code">, </span><span class="hl-number">2</span><span class="hl-code">, </span><span class="hl-number">8</span><span class="hl-code">, </span><span class="hl-number">5</span><span class="hl-code">, </span><span class="hl-number">9</span><span class="hl-code">, </span><span class="hl-number">1</span><span class="hl-brackets">}</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment">array suplimentar (ca ajutor)</span> int<span class="hl-brackets">[</span><span class="hl-brackets">]</span> <span class="hl-identifier">extraArray</span><span class="hl-code"> = </span><span class="hl-reserved">new</span> int<span class="hl-brackets">[</span><span class="hl-identifier">someData</span><span class="hl-code">.</span><span class="hl-identifier">length</span><span class="hl-brackets">]</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment">apeleaza functia mergesort</span> <span class="hl-identifier">mergeSort</span><span class="hl-brackets">(</span><span class="hl-identifier">someData</span><span class="hl-code">, </span><span class="hl-identifier">extraArray</span><span class="hl-code">, </span><span class="hl-number">0</span><span class="hl-code">, </span><span class="hl-identifier">someData</span><span class="hl-code">.</span><span class="hl-identifier">length</span><span class="hl-code">-</span><span class="hl-number">1</span><span class="hl-brackets">)</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment">afiseaza rezultatul</span> <span class="hl-reserved">for</span><span class="hl-brackets">(</span>int <span class="hl-identifier">pr</span><span class="hl-code"> : </span><span class="hl-identifier">someData</span><span class="hl-brackets">)</span> <span class="hl-brackets">{</span> <span class="hl-identifier">System</span><span class="hl-code">.</span><span class="hl-identifier">out</span><span class="hl-code">.</span><span class="hl-identifier">print</span><span class="hl-brackets">(</span><span class="hl-identifier">pr</span><span class="hl-brackets">)</span><span class="hl-code">; </span><span class="hl-brackets">}</span> |
Din nou, experimenteaza schimband valorile din array si observa rezultatul programului.
Pentru inceput, algoritmul recursiv poate fi dificil de inteles si in mod sigur necesita ceva practica, dar atunci cand vei reusi, vei descoperi ca poti identifica solutii destul de rapide pentru anumite probleme. Este indicat ca la scrierea unei metode recursive sa incepi de la cazul cel mai simplu, apoi sa te ocupi de pasii care conduc catre acesta de fiecare data cand metoda este executata.
Cautarea
Deseori va trebui sa gasesti un anumit element intr-o structura de date dintr-un motiv sau altul. Daca datele din array nu sunt sortate, singurul mod pentru a efectua aceasta este sa verifici fiecare element pe rand. In schimb, daca dispui de un array sortat, poti folosi o metoda de cautare binara, cum este cea de mai jos:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
<span class="hl-comment">//</span><span class="hl-comment">metoda de cautare </span> <span class="hl-comment">//</span><span class="hl-comment">primul parametru reprezinta array-ul in care cautam</span> <span class="hl-comment">//</span><span class="hl-comment">cel de-al doilea este elementul cautat</span> <span class="hl-reserved">public</span> static int <span class="hl-identifier">binarySearch</span><span class="hl-brackets">(</span><span class="hl-identifier">String</span><span class="hl-brackets">[</span><span class="hl-brackets">]</span> <span class="hl-identifier">theData</span><span class="hl-code">, </span><span class="hl-identifier">String</span> <span class="hl-identifier">wanted</span><span class="hl-brackets">)</span> <span class="hl-brackets">{</span> <span class="hl-comment">//</span><span class="hl-comment">-1 inseamna ca elementul nu a fost gasit</span> int <span class="hl-identifier">foundIndex</span><span class="hl-code">=-</span><span class="hl-number">1</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment">retine capetele intervalului de cautare</span> int <span class="hl-identifier">top</span><span class="hl-code"> = </span><span class="hl-identifier">theData</span><span class="hl-code">.</span><span class="hl-identifier">length</span><span class="hl-code">-</span><span class="hl-number">1</span><span class="hl-code">; </span>int <span class="hl-identifier">bottom</span><span class="hl-code"> = </span><span class="hl-number">0</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment">parcurge array-ul, divizand intervalul de cautare</span> <span class="hl-reserved">while</span><span class="hl-brackets">(</span><span class="hl-identifier">bottom</span><span class="hl-code"><=</span><span class="hl-identifier">top</span><span class="hl-brackets">)</span> <span class="hl-brackets">{</span> <span class="hl-comment">//</span><span class="hl-comment">calculeaza mijlocul sectiunii analizate</span> int <span class="hl-identifier">middle</span><span class="hl-code"> = </span><span class="hl-brackets">(</span><span class="hl-identifier">top</span><span class="hl-code">+</span><span class="hl-identifier">bottom</span><span class="hl-brackets">)</span><span class="hl-code">/</span><span class="hl-number">2</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment">compara elementul din mijloc cu elementul cautat </span> int <span class="hl-identifier">comp</span><span class="hl-code"> = </span><span class="hl-identifier">theData</span><span class="hl-brackets">[</span><span class="hl-identifier">middle</span><span class="hl-brackets">]</span><span class="hl-code">.</span><span class="hl-identifier">compareTo</span><span class="hl-brackets">(</span><span class="hl-identifier">wanted</span><span class="hl-brackets">)</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment">daca elementul din mijloc este egal cu elementul cautat, returneaza indexul sau</span> <span class="hl-reserved">if</span><span class="hl-brackets">(</span><span class="hl-identifier">comp</span><span class="hl-code">==</span><span class="hl-number">0</span><span class="hl-brackets">)</span> <span class="hl-reserved">return</span> <span class="hl-identifier">middle</span><span class="hl-code">; </span><span class="hl-comment">/*</span><span class="hl-comment"> daca elementul din mijloc este mai mare, * atunci elementul cautat se afla in prima jumatate * altfel se afla in cea de-a doua jumatate </span><span class="hl-comment">*/</span> <span class="hl-reserved">else</span> <span class="hl-reserved">if</span><span class="hl-brackets">(</span><span class="hl-identifier">comp</span><span class="hl-code">></span><span class="hl-number">0</span><span class="hl-brackets">)</span> <span class="hl-comment">//</span><span class="hl-comment">mijlocul este mai mare</span> <span class="hl-identifier">top</span><span class="hl-code">=</span><span class="hl-identifier">middle</span><span class="hl-code">-</span><span class="hl-number">1</span><span class="hl-code">; </span><span class="hl-reserved">else</span> <span class="hl-comment">//</span><span class="hl-comment">mijlocul este mai mic</span> <span class="hl-identifier">bottom</span><span class="hl-code">=</span><span class="hl-identifier">middle</span><span class="hl-code">+</span><span class="hl-number">1</span><span class="hl-code">; </span><span class="hl-brackets">}</span> <span class="hl-comment">//</span><span class="hl-comment">am terminat cautarea</span> <span class="hl-reserved">return</span> <span class="hl-identifier">foundIndex</span><span class="hl-code">; </span><span class="hl-brackets">}</span> |
Acum apeleaza aceasta functie din metoda main:
1 2 3 4 5 6 7 8 |
<span class="hl-comment">//</span><span class="hl-comment">array ordonat</span> <span class="hl-identifier">String</span><span class="hl-brackets">[</span><span class="hl-brackets">]</span> <span class="hl-identifier">sortedStrings</span><span class="hl-code"> = </span><span class="hl-brackets">{</span><span class="hl-quotes">"</span><span class="hl-string">aubergine</span><span class="hl-quotes">"</span><span class="hl-code">, </span><span class="hl-quotes">"</span><span class="hl-string">carrot</span><span class="hl-quotes">"</span><span class="hl-code">, </span><span class="hl-quotes">"</span><span class="hl-string">courgette</span><span class="hl-quotes">"</span><span class="hl-code">, </span><span class="hl-quotes">"</span><span class="hl-string">leek</span><span class="hl-quotes">"</span><span class="hl-code">, </span><span class="hl-quotes">"</span><span class="hl-string">onion</span><span class="hl-quotes">"</span><span class="hl-code">, </span><span class="hl-quotes">"</span><span class="hl-string">potato</span><span class="hl-quotes">"</span><span class="hl-code">, </span><span class="hl-quotes">"</span><span class="hl-string">turnip</span><span class="hl-quotes">"</span><span class="hl-brackets">}</span><span class="hl-code">; </span><span class="hl-comment">//</span><span class="hl-comment">apeleaza metoda de cautare - returneaza -1 daca elementul nu este gasit</span> int <span class="hl-identifier">searchResult</span><span class="hl-code"> = </span><span class="hl-identifier">binarySearch</span><span class="hl-brackets">(</span><span class="hl-identifier">sortedStrings</span><span class="hl-code">, </span><span class="hl-quotes">"</span><span class="hl-string">potato</span><span class="hl-quotes">"</span><span class="hl-brackets">)</span><span class="hl-code">; </span><span class="hl-identifier">System</span><span class="hl-code">.</span><span class="hl-identifier">out</span><span class="hl-code">.</span><span class="hl-identifier">println</span><span class="hl-brackets">(</span><span class="hl-quotes">"</span><span class="hl-string">gasit la indexul: </span><span class="hl-quotes">"</span><span class="hl-code">+</span><span class="hl-identifier">searchResult</span><span class="hl-brackets">)</span><span class="hl-code">;</span> |
Experimenteaza cautand diverse elemente din array. In plus, poti verifica cate iteratii ale buclei sunt necesare de fiecare data, incluzand o instructiune System.out.print in bucla din metoda binarySearch. In general este o practica buna sa incluzi astfel de instructiuni in codul tau, pentru a verifica in mod exact ce se intampla in fiecare stadiu al programului; poate fi de ajutor mai ales la corectarea programelor mai mari.
Desi multe tipuri de date din Java includ metode de sortare si de cautare, poate fi de ajutor pentru optimizarea programelor proprii sa te gandesti la algoritmii implicati. Totodata, cand trebuie sa iti definesti propriile tipuri de date, s-ar putea sa fie nevoie sa implementezi astfel de metode. Exista numeroase abordari in vederea sortarii si a cautarii in Java, exemplele de mai sus fiind doar introductive.