| Hemorrhoid pain relief

Algoritmi.

Prezentarea algoritmilor de cautare.

Cuprins:
1. Cautarea liniara.
2. Tehnica fanionului.
3. Cautarea binara (logaritmica).
4. Cautarea binara performanta.
5. Cautarea prin interpolare.

1. Cautarea liniara >>>

In stinta calculatoarelor, cautarea liniara este privita ca un algoritm de cautare segvential, si care are rolul de a cauta o valoare oarecare aflata intr-un tablou de date.Acest tip de cautare opereaza prin a verifica fiecare element al unui tablou prin segvente de timp, pana cand se gaseste un termen din tablou care are valoarea numerica egala cu valoarea termenului cautat.Cautarea liniara ruleaza dupa principiul functiei O(N), unde N este numarul de comparatii care se realizeaza intr-un tablou pentru a afla termenul cu valoarea cautata.Daca datele din lista sunt distribuite aleator, atunci va fi necesar un timp mediu de N/2 comparatii pentru a afla termenul cautat.Cel mai bun caz este acela in care termenul cu valoarea cautata in tablou, este identica cu prima valoare gasita in tablou,in acest fel efectuandu-se numai o singura comparare.Cel mai ineficient caz in care se poate aplica algoritmul cautarii liniare este acela in care valoara cautata nu este in tablou, sau ultimul termen din tablou are valoarea identica cu valoarea cautata.In acest caz algoritmul realizeaza un numar de N comparatii,ceea ce este un dezavantaj deoarece tabloul poate contine un numar mare de termeni, iar algoritmul devine ineficient testand si cautand intr-un numar asa mare de termeni.Simplitatea cautarii liniare este modalitata prin care numai un numar mic de termeni sunt cautati, iar avantajul este ca se realizeaza un comportament mult mai eficient decat metodele complexe de cautare, care necesita multe aranjamente asa cum sunt algoritmii de sortare a termenilor ce trebuiesc cautati,sau alte structuri de date complexe.Deasemeni este un algoritm de cautare mult mai eficient decat structurile de date a caror date de intrare necesita verificari fregvente.Alta posibilitate avantajoasa in care se poate aplica algoritmul cautarii liniare este aplicata in tablouri care se pot ordona, deoarece o valoara oarecare este mult mai usor de aflat intr-un tablou ordonat care prezinta valoarea cautata ca fiind pintre primele.

Functionarea cautarii liniare:

* Pentru fiecare termen din lista se verifica daca in lista termenilor de cautat se gaseste alte valori egale cu termenul cautat.
* Daca termenul de cautat a fost gasit: atunci se returneaza locatia la care a fost gasit (indexul).
* Daca termenul nu a fost gasit: se continua cautarea pana se ajunge la sfarsitul listei.
* Daca nici asa nu a fost gasit: atunci se va semnala ca termenul de cautat nu a fost gasit in lista.
* Returneaza valoarea -1, ca semn ca valoarea nu este in lista.

Algoritm de cautare lininara implementat in limbajul Pascal.
Se compara pe rind elementele tabloului cu x pina cind, fie se gaseste egalitatea a[i]=x, fie s-a ajuns la sfirsitul tabloului:

procedure CautareLiniara;
var i:1..N;
begin
i:=1;
while (a[i] < > x) and (i < N) do i:=i+1;
if a[i] < > x then { nu exista elementul cautat}
else { elementul cautat este pe pozitia i }
end;

Algoritm de cautare liniara implementat in cod Java.
Se declara a[ ] ca fiind un tablou al numerelor de tip intreg care trebuiesc cautate.
Valoarea intreaga "termenCautat" reprezinta numarul ce se doreste a fi gasit.functia returneaza pozitia valorii daca aceasta s-a gasit, si in caz contrar va returna -1:

private int CautareLiniara(int a[], int termenCautat)
{ 
for(int i=0;i {
if(termenCautat == a[i]) // termenul de cautat se afla in tablou?
{
return i;//elementul de cautat se afla la pozitia i 
}
}
return -1;// elementul de cautat nu se afla in lista
}

Algoritm de cautare lininara implementat in cod OCaml.
Se defineste o functie numita "mem" care returneaza valoarea logica "true" (adevarat) daca termenul dat spre cautare exista in lista.In caz contrar, se va returna valoarea "false" (fals) daca nu exista in lista.Aceasta functie poate fi definita astfel:

 let rec mem x =function 
[] -> false
| h :: t ->h=x || mem x t


Algoritm de cautare implementat in programul de sistemul algebric pentru calculator Mathematica:

Mem[x_, {__, x__, __}]:= True 
Mem[_, _] := False

2. Tehnica fanionului >>>

Tabloul "a" se prelungeste cu inca un element (fanion) caruia i se asigneaza valoarea x, apoi se aplica metoda de cautare liniara.Avantajul acestei metode consta in simplificarea condiþiei de ciclare, in sensul ca nu mai este nevoie sa se verifice daca indicele nu depaseste dimensiunea tabloului, deoarece in tablou exista sigur cel putin un element cu valoarea cautata.

procedure Fanion;
var a:ARRAY [1..N+1] of TipElement;
i:1..N+1;
begin
i:=1;a[N+1]:=x;
while a[i]<>x doi:=i+1;
if i>N then { nu exista elementul cautat }
else { elementul cautat se afla pe pozitia i }
 end;

3. Cautarea binara (logaritmica) >>>

Un algoritm de cautare binara este o tehnica aplicata in stinta calculatoarelor, ca fiind o metoda care gaseste o valoare oarecare intr-un tablou sortat in prealabil,si care consta in injumatatirea periodica a tabloului pana cand se afla valoarea cautata.Injumatatirea tabloului presupune aflarea unei valori care va reprezenta mijlocul tabloului;iar valoarea de cautat se va compara cu valoarea din mijlocul tabloului.Daca in urma compararii a rezultat ca valoarea cautata este mai mica decat valoarea de mijloc a tabloului, atunci cautarea se va aplica in jumatatea tabloului situata inaintea valorii de centru (mijloc) a tabloului.Astfel se va proceda pana cand valoarea cautata devine mijlocul tabloului, aceasta indicand ca valoarea care s-a cautat este in tablou.Daca valoarea cautata este mai mare decat valoarea de mijloc a tabloului, atunci cautarea se va aplica in jumatatea tabloului situata dupa valoarea de mijloc.Si algoritmul realizeaza injumatatiri repetate pana cand valoarea de cautat devine mijlocul tabloului, si care demonstreaza ca valoarea se gaseste in tablou.Astfel dar,cautarea binara se aplica pentru tablouri ordonate, principiul ei constind in injumatatirea repetata a intervalului in care se cauta elementul dorit.Necesitatea ca tabloul sa fie ordonat implica faptul ca elementele sale au o componenta (cheie) ce apartine unui tip scalar, iar cautarea se face dupa aceasta componenta. Uneori se foloseste un alt mod de calcul al lui d, astfel incit se simplifica conditia de ciclare.Aceasta tehnica are avantajul rapiditatii: numarul de comparatii necesare este cel mult log₂(N), fiind un algoritm logaritmic si se executa intr-un interval de timp O(log n),fiind necesare 1 + log₂N iteratii pentru a returna un raspuns.In cele mai multe cazuri este considerat mai rapid decat tehnica de cautare liniara, fiind posibila implementarea cu recursii si iteratii.In unele limbaje este mult mai elegant ca pentru acest tip de cautare sa se foloseasca recursivitatea ca metoda, insa in limbajele bazate pe programarea in cod C este necesar sa se foloseasca o instructiune-bucla, deoarece stiva folosita se incrementeaza la fiecare recursie.

Algoritm de cautare binara implementat in cod Pascal.

procedure CautareBinara;
var s,d,m:Integer;
begin
s:=1; d:=N;
if (x<=a[d]) and (x>=a[s]) then begin
repeat
m:=(s+d) div 2;
if x>a[m] then s:=m+1  else d:=m-1
until (a[m]=x) or (s>d);
if a[m]=x then { elementul cautat se afla pe pozitia m }
else { nu exista elementul cautat }
 end;

Implementarea algoritmului de cautare binara in cod C.
Atata timp cat prima jumatate a tabloului este sunt prezenti termeni care au valori mai mici sau egali cu ultima parte a tabloului si totodata este mai mica sau egala cu valoarea cheii de cautat, atunci mijlocul tabloului este suma dintre locaþiile valorilor primei parti a tabloului si ultima parte a tabloului impartita la 2.Daca in cadrul valorilor din prima jumatate a tabloului s-a gasit termenul cu valoarea cautata atunci se va semnala gasirea cheii.Daca in cadrul valorilor termenilor din prima jumatate a tabloului sunt mai mici decat valoarea termenului cu valoarea cautata, atunci se va aplica procedeul cautarii in a doua jumatate a tabloului.Daca cheia s-a gasit se va semnala gasirea ai, daca nu, atunci se va semnala ca valoarea termenului cautat nu se afla in tablou:

int cautare_binara(int tab[], int gasit, int primul, int ultim)
{
int mijloc, gasit;
gasit = 0;
while((primul <= ultim) && !gasit)
{
mijloc = (primul + ultim) / 2;
if (tab[mijloc] == gasit) 
gasit = 1;
else if (tab[mijloc] < gasit) 
primul  = mijloc+1;
else ultim = middle - 1;
 }
if (gasit) 
return mijloc; else
return -1; 
}

Exemplu pentru algoritmul de cautare binara.
Se dau 9 numere intregi, care vor avea locatiile de la 0 la 8, cu valori diferite.In lista acestor numere trebuie aflat termenul care are valoarea intreaga 37:

Acum se urmaresc toate valorile termenilor aflati la inceputul si sfarsitul tabloului.Se va aduna locatiile termenilor aflati in interiorul tabloului si se vor impartii la 2 pentru a afla mijlocul tabloului.Tabloul este ordonat crescator, iar in mijlocul tabloului se afla termenul cu valoarea medie din tablou 45, care se afla in locatia 4:

Acum se compara valoarea 37 cu valoarea medie aflata in mijlocul tabloului: este 37 egal cu 45? 37 este mai mic ca si 45: se imbunatateste ultimul pointer ca fiind egala cu pozitia termenului din mijlocul tabloului din care se va scade o unitate, si se va reordona tabloul.Adica operatia de cautare se va localiza in jumatatea care contine valori mai mici ca si 37, deoarece tabloul este ordonat si valoarea termenului de cautat 37, este mai mic decat valoarea medie a tabloului 45:

Se compara termenul nostru de cautat 37 cu valoaera medie 35, aflata in locatia de mijloc a acestei parti.In aceasta noua jumatate a tabloului (listei) valoarea medie este 35: este termenul nostru 37 egal cu 35? 37 este mai mare ca si 35 si rezulta o noua comapare a lui 37 cu primul si ultimul termen din tablou, rezultand o noua injumatatire a tabloului cu o noua valoare medie:

Se compara mijlocul tabloului cu termenul nostru de cautat, iar valoarea se afla in tablou:

4. Cautare binara performanta >>>

Implementarea algoritmului de cautare binara performanta in cod Pascal:

procedure CautareBinaraPerform;
begin
s:=1; d:=N+1;
repeat
m:=(s+d) div 2;
if x>a[m] then s:=m+1
else d:=m
until s>=d;
if d>N then { nu exista elementul cautat }
else if x=a[d] then { elementul cautat se afla pe pozitia d }
else { nu exista elementul cautat }
 end;

Implementarea alegoritmului de cautare binara performanta in cod C:

int cautare_binara(char gasit, char tab[], int start, int finish)
{
/* Aflarea mijlocului tabloului */
int middle = (start + finish) / 2;

if (start > finish) return -1;
if (arr[middle] < find)
{ 
return binary_search(find, arr, middle, finish);
}
else if (arr[middle] > find) 
{
return binary_search(find, arr, start, middle);
} 
else { return middle; }

}

5. Cautarea prin interpolare >>>

Este similara cu cautarea binara, dar foloseste o alta formula pentru calculul lui "m", si anume: m:=s+(x-a[s])*(d-s) div (a[d]-a[s]) ceea ce conduce la o delimitare mai rapida a zonei din tablou in care s-ar putea gasi x. Ca principiu, metoda este inspirata dupa procedeul cautarii intr-o carte de telefon.Aceasta metoda este eficienta in cazul in care N este foarte mare si valorile elementelor tabloului au o distributie uniforma in intervalul a[1],...,a[N]. Numarul de cautari in acest caz este de ordinul lg(lgN).Aplicarea cautarii prin interpolare necesita ca elementul de cautat, x, sa se afle in interiorul intervalului a[1],..,a[N], altfel apare riscul ca valoarea calculata a lui "m" sa depaseasca N.

Implementarea algoritmului de cautare prin interpolare in cod Pascal.

procedure CautareInterpolare;
var s,d,m: Longint;
begin
s:=1; d:=N;
{ if (x<=a[d]) and (x>=a[s]) then begin }
repeat
m:=s+(x-a[s])*(d-s) div (a[d]-a[s])
if x>a[m] then s:=m+1
else d:=m-1
until (a[m]=x) or (s>=d) or (a[s]=a[d]) or (x < a[s]) or (x > a[d]);
if a[m]=x then {elementul cautat se afla pe pozitia m}
else { nu exista elementul cautat }
 end;

Implementarea algoritmului de cautare prin interpolare in cod Java.

public int cautareInterpolare(int[] tab, int gasit) 
{
/* Se va returna pozitia lui "gasit" in tabloul sortat "tab",*/
/*in caz contrar se va returna valoarea -1*/
/* va semnala ca termenul de cautat nu a fost gasit*/ 
int low = 0;
int high = tab.length - 1;
int mid;
while (tab[low] < gasit && tab[high] >= gasit)
{
mid = low + ((gasit - tab[low]) * (high - low)) / (tab[high] - tab[low]);
if (tab[mid] < gasit)
low = mid + 1;
else if (tab[mid] > gasit).high = mid - 1;
else return mid;
}
if (tab[low] == gasit)
return low;
else return -1; // nu s-a gasit
}

Aceasta metoda este eficienta in cazul in care N este foarte mare si valorile elementelor tabloului au o distributie uniforma in intervalul a[1],...,a[N]. Numarul de cautari in acest caz este de ordinul lg(lg N).Aplicarea cautarii prin interpolare necesita ca elementul de cautat, x, sa se afle in interiorul intervalului a[1],..,a[N], altfel apare riscul ca valoarea calculata a lui "m" sa depaseas- ca N.

Structuri de date abstracte | SDA Arbori | SDA Arbori Binari | SDA Arbori Multicai | SDA Arbori Optimi | SDA Graf | Traversarea grafurilor | SDA Graf Ponderat | SDA Graf Orientat | SDA Lista Inlantuita | SDA Tablou Asociat | Despre algoritmi. | Algoritmi de cautare neinformata, cautarea inforamata,cautarea in liste,in grafuri, in SQL-uri | Algoritmi de cautare liniara, binara, interpolare | Prezentare Algoritmi Sortare | Sortare Insertie cu Pas Variabil (Shellsort) | Sortarea Prin Ansamble (Heapsort) | Sortarea Prin Insertie (Insertionsort) | Sortarea Prin Interclasare (Mergesort) | Sortarea Prin Interschimbare (Bubblesort) | Sortarea Prin Selectie (Selectionsort) | Sortarea Rapida (Quicksort)

Inapoi la pagina principala