Clasa a V-a lecția 41 - 10 iun 2014
Tema - rezolvări
Rezolvare aici [1]
Lecție
Căutare binară
Căutarea binară este un mod mai rapid de a căuta pe ce poziție se află un element într-un vector.
Ce complexitate are căutarea clasică a unui element într-un vector? Deoarece elementul se poate afla pe orice poziție în vector, iar noi căutăm liniar elementele, unul după altul, rezultă că, pe medie, vom face n / 2 comparații atunci cînd elementul se află în vector. Putem să rezolvăm această problemă mai rapid?
Putem, cu condiția ca vectorul să fie ordonat. Să ne folosim de o analogie: cum căutam un cuvînt în dicționar? Dicționarul are circa 60000 de cuvinte. Dacă am căuta la rînd, liniar, ne-ar lua zile să-l găsim. Și atunci deschidem dicționarul undeva, să spunem la mijloc. Ne uităm la ce literă sîntem, să spunem 'm'. Dacă noi căutăm 'gorilă', știm că 'g' < 'm', deci vom căuta la stînga, eliminînd jumate din dicționar. Vom continua la fel, deschidem undeva la jumate în jumatea rămasă și vedem iarăși la ce literă sîntem. Atunci cînd ajungem la litera 'g' vom continua cu a doua literă. În acest fel vom găsi cuvîntul rapid, probabil în jumate de minut, în loc de zile.
Aceasta este metoda căutării binare. Dacă vectorul nostru este ordonat, putem căuta mai întîi la jumate. Dacă elementul din vector este mai mic decît elementul căutat înseamnă că trebuie să ne uităm în jumătatea dreaptă, altfel ne uităm în cea stîngă. Apoi, în vectorul rămas, vom repeta algoritmul. La fiecare pas vom înjumătăți numărul de numere rămase. Ne oprim atunci cînd subvectorul rămas are fix un element. Dacă este elementul căutat, returnăm poziția sa, altfel el nu există. Iată o implementare posibilă:
Atenție: stinga este prima poziție in vectorul căutat, iar dreapta este prima poziție în afara vectorului căutat. Dacă respectați această convenție evitați bug-urile de final de căutare cînd indicii rămîn pe loc și o condiție incorectă in while poate să ducă la o buclă infinită.
stinga = 0;
dreapta = n;
while ( dreapta - stinga > 1 ) {
mijloc = (stinga + dreapta) / 2;
if ( v[mijloc] > e )
dreapta = mijloc;
else
stinga = mijloc;
}
if ( e == v[stinga] ) {
... găsit, procesare aici ...
}
Selecție
Dat un șir de n numere și o poziție k în acel șir să se spună ce element s-ar afla pe acea poziție dacă șirul ar fi sortat (ordonat crescător).
Ideea de rezolvare este să folosim primul pas al algoritmului quicksort și anume pivotarea. Prin pivotare înțelegem separarea vectorului original în două regiuni: cea din stînga cu numere mai mici sau egale cu pivotul, iar cea din dreapta cu numere mai mari sau egale cu pivotul (nu este o greșeală, în ambele părți putem avea numere egale cu pivotul). Pivotul poate fi ales la întîmplare, orice element din vector. Odată ce avem subșirurile v[1..i] și v[i+1..j] ne vom întreba în ce interval se află k și vom relua problema selecției în acel interval, mai mic. Cîte operații va face acest algoritm? pe medie doar n. Pe cazul cel mai rău n2.
Iată o implementare a pivotării, în care căutăm în paralel în stînga un element mai mare, iar în dreapta unul mai mic, apoi le interschimbăm. Pivotul nu ajunge neapărat pe poziție:
int v[1000000];
int main() {
FILE *fin, *fout;
int n, k, i, begin, end, b, e, pivot, aux;
fin = fopen( "selectie.in", "r" );
fscanf( fin, "%d%d", &n, &k );
for ( i = 0; i < n; i++ )
fscanf( fin, "%d", &v[i] );
fclose( fin );
k--;
begin = 0;
end = n - 1;
while ( begin < end ) {
b = begin;
e = end;
pivot = v[(begin + end) / 2]; // alegem un pivot la jumatea vectorului
while ( b <= e ) {
while ( v[b] < pivot ) b++;
while ( v[e] > pivot ) e--;
if ( b <= e ) {
aux = v[b]; v[b] = v[e]; v[e] = aux;
b++; e--;
}
}
// acum [begin..e] sint mai mici sau egale cu pivotul
// si [b..end] sint mai mari sau egale cu pivotul
if ( k <= e )
end = e;
else if ( k >= b )
begin = b;
else
begin = end = k;
}
fout = fopen( "selectie.out", "w" );
fprintf( fout, "%d\n", v[k] );
fclose( fout );
return 0;
}Temă
Încercați să implementați algoritmii prezentați astăzi. Uitați-vă pe program, înțelegeți-l, apoi implementați-l voi, fără a vă uita la soluție.
Rezolvări aici [2]
