Clasa a IX-a lecția 11 - 18 ian 2020

From Algopedia
Revision as of 07:43, 18 January 2020 by Teodor (talk | contribs) (→‎Varianta 1)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Clasament teme lecțiile 1 - 10

Clasamente avansați

Avansați Infoarena
Avansați Varena

Clasamente începători

Începători Varena
Începători Infoarena

Lecție

Căutare binară

Varianta 1

Sursa: IQAcademy

Căutarea binară este un mod mai rapid de a căuta pe ce poziție se află un element într-un vector. Căutarea clasică într-un vector de n elemente are o complexitate de O(n). Putem micșora această complexitate dacă vectorul este 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ă:

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 ...
}

Observație importantă: stinga este prima poziție in vectorul căutat, iar dreapta este prima poziție în afara vectorului căutat.

Ce complexitate are căutarea binară? Să observăm că la fiecare iterație a buclei while diferența dintre dreapta și stinga se reduce la jumate. Ne vom opri atunci cînd ea devine 1. Bucla se va executa, deci, de cîte ori putem împărți diferența la doi, deci O(log n) unde n este numărul de elemente pe care se face căutarea.

Varianta de program de mai sus găsește ultima apariție a lui e. Ea poate fi adaptată să găsească prima apariție, gîndiți-vă cum. De asemenea, căutarea binară poate fi adaptată să găsească poziția la care s-ar putea insera un element e în vector.

Atenție! Căutarea binară este faimoasă pentru ușurința cu care o puteți greși. Pentru a vă asigura că nu veți avea greșeli la implementare respectați următoarele reguli:

  1. Intervalul de căutare să fie închis la un capăt și deschis la celălalt, iar testul de oprire să fie ca diferența dintre capete să fie strict mai mare ca unu. 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ă.
  2. Comparația cu elementul să fie totdeauna de tip strict (mai mic sau mai mare, nu mai mic sau egal).
  3. Cînd comparația este adevărată se va muta în mijloc capătul deschis al intervalului.

Varianta 2

O altă variantă a acestui algoritm se folosește de faptul că orice număr poate fi scris ca sumă de puteri ale lui 2 (având în vedere descompunerea în baza 2). Mai precis, orice poziție din vector poate fi scrisă ca sumă de puteri ale lui 2. Pentru un vector v de n elemente, algoritmul funcționează astfel:

   1. Găsește cea mai mare putere a lui 2 mai mică sau egală cu n. O notăm cu step.
   2. Setează poziția curentă de căutare la stânga vectorului, adică -1. O notăm cu pos.
   3. Testăm elementul v[pos + step]:
       3.1. Dacă este mai mare decât elementul căutat, ne deplasam cu poziția curentă: pos += step.
       3.2. Dacă este mai mic decât elementul căutat, nu vrem să ne deplasăm pentru ca am trece de el.
   4. Înjumătățim step: step /= 2
   5. Ne întoarcem la pasul 3, oprindu-ne când step devine 0.

O metodă de implementare:

...
int pos = -1, step = 1;

// Calculam cea mai mare putere a lui 2, mai mica sau egala decat n
while (step * 2 <= n)
  step *= 2;

while (step > 0) {
  if (pos + step < n && v[pos + step] <= e)
    pos += step;
  step /= 2;
}

if (pos != -1 && v[pos] == e) {
  // gasit!
}

Atenție La fiecare pas, trebuie să ne asigurăm că nu ieșim din limitele vectorului! Atenție La final, trebuie să ne asigurăm atât că pos nu a rămas la poziția inițială de -1, cât și că elementul de pe poziția pos este cel căutat.

Această variantă de implementare ne va întoarce tot ultima apariție a lui e. Gândiți-vă ce trebuie schimbat pentru a întoarce prima poziție.

Observație Nu este neapărat necesar să calculăm cea mai mare putere a lui 2 mai mică sau egală decât n. Putem seta o valoare implicită mai mare decât maximul lui n. Exemplu:

...
int pos = -1, step = 1 << 20; // 2^20, in cazul in care n nu depaseste ~1 milion
...

Aplicații

Sunt multe aplicații care se folosesc de această tehnică. Vom discuta aici câteva, după care vă veți apuca să le lucrați. Sunteți liberi să folosiți orice variantă a algoritmului, atât timp cât vă asigurați că o înțelegeți bine.

Căutare binară pe un vector

varena - cautbin
Am descris mai sus cum se poate folosi căutarea binară pentru a căuta un număr într-un vector ordonat. Aceasta este o problemă clasică pe care veți învăța să folosiți diverse moduri de a căuta binar.

Căutare binară pe o funcție

infoarena - fact
Căutarea unui element într-un vector nu este singura întrebuințare a căutarii binare. Putem folosi acest algoritm pentru a afla în ce punct are o funcție (matematică sau... "informatică") o anumită valoare. Evident, funcția trebuie să monotonă. Să luăm de exemplu funcția:

  • f(x) = numărul de zero-uri în care se termină x!

Funcția este crescătoare, deci dacă dorim să găsim cel mai mic număr natural pentru care f(x) are e zerouri, putem folosi căutarea binară. Este mult mai rapid decăt parcurgem toate numerele de la stânga la dreapta începând cu 1, să calculăm valoarea lui f(x) pentru fiecare în parte și să ne oprim când dăm de o valoare egală cu e.

Observație Nu trebuie să generăm toate valorile funcției înainte, nu trebuie să le știm pe toate. Ne interesează doar valorile în punctele prin care trecem folosind căutarea binară.

Căutare binară a răspunsului

infoarena - transport

Sunt multe probleme în care ni se cere să găsim valoarea minimă / maximă care respectă o anumită proprietate. Să notăm astfel:

  • f(x) = 0, dacă x nu respectă proprietatea
  • f(x) = 1, dacă x respectă proprietatea

Dacă funcția noastră este monotonă, ea va arăta ceva de genul următor:

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |

În acest moment, este evident că putem aplica o căutare binară pe ea, vom verifica la fiecare pas valoarea funcției în poziția la care suntem în căutare și vom decide dacă ne vom deplasa la stânga sau la dreapta. Altfel spus, la fiecare pas vom verifica dacă valoarea la care am ajuns respectă sau nu proprietatea problemei.

Temă

Începători

varena - cautbin
infoarena - fact

Avansați

varena - cautbin
infoarena - fact
infoarena - transport
infoarena - triang
infoarena - loto
infoarena - gfact