Divide-et-Impera

Cerinta: Se dau n numere naturale. Să se afișeze al k-ulea cel mai mic element din șir.

Rezolvarea este compusa din doua functii importante, prima sorteaza crescator vectorul iar a doua cauta elementul de pe pozitia k.

Primul pas facut pentru rezolvarea problemei este definirea functiei de sortare. Pentru a aplica tehnica Divide et impera am folosit sortarea Mergesort deoarece din punct de vedere al complexitatii in cel mai rau caz aceasta metoda are O(nlogn) si functioneaza mai rapid pe vectori de dimensiuni mari. Dezavantajul este acela ca foloseste un vector auxiliar care scade eficienta din punct de vedere al memoriei.

Funcția de sortare:

- Am definit functia numita mergesort care returneaza vectorul sortat crescator:

merge_sort(st,dr)

- Se divide vectorul v de dimensiune n in doi vectori de dimensiune n/2 si definim mijlocul: mij =(st+dr)/2

- Se reapeleaza functia merge_sort pentru a cauta in prima jumatate de la stanga pana la mijloc: merge_sort(s,mij)

- Se reapeleaza functia merge_sort pentru a cauta in a doua jumatate de la mij+1 pana la dreapta: merge_sort(mij+1,dr)

- Se interclaseaza seubvectorii sortati prin apelarea functiei: interclasare(st,mij,dr)

Funcția de cautare binara:

Algoritmul de cautare binara foloseste doar etapa de Divide fara partea de recombinare a solutiilor deoarece imparte vectorul in doua jumatati de dimensiune n/2, fixeaza mijlocul iar apoi cauta doar intr-o secventa in functie de valoare mijlocului, reducand practic la jumatate numarul de operatii.

Pentru a cauta al k-ulea element in secventa v[st], v[st+1]...v[mij], v[mij+1]...v[n] a tabloului v, cat timp st <= dr, exista 3 cazuri:

 k = mij - am gasit elementul si returnam v[mij], este cazul cel mai favorabil;

 k < mij - cautam doar in secventa v[st] .v[mij-1];

 k > mij - cautam doar in secventa v[mij+1] .v[dr];