[C] Divide et Impera - Căutarea binară

[TLG George]

Metoda Divide et Impera constă în împărțirea repetată a unei probleme în două sau mai multe sub-probleme de același tip și apoi combinarea sub-problemelor rezolvate, în final obținându-se soluția problemei inițiale. 

 

O aplicație importantă a acestei metode este Căutarea binară.

 

Să considerăm un șir ordonat de elemente A = ( a1, a2, ... , an), se dorește a știi dacă un element k se află în șirul A. Procedura poate fi sintetizată prin următorii pași și exemplificată în figura de mai jos.

 

1. p = 1 si q = n (p reprezintă poziția primului element din șir și q reprezintă poziția ultimului element din șir)
2. daca p > q => k nu este prezent
3. se identifica mijlocul intervalului (p, q); m = (p + q) / 2
4. daca am = k => k este prezent
5. daca am > k => aplica pasul 2 pentru sub-sirul Ap,m (cu alte cuvinte dacă elementul din mijlocul șirului este mai mare decât elementul k căutat de noi, vom căuta elemntul k doar în partea stângă de la jumătate, deci automat problema s-a împărțit in două)
6. daca am < k => aplica pasul 2 pentru sub-sirul Am+1,q (cu alte cuvinte dacă elementul din mijlocul șirului este mai mic decât elementul k căutat de noi, vom căuta elemntul k doar în partea dreaptă de la jumătate, deci automat problema s-a împărțit in două)

 

Apoi pașii se repetă.

 

 

Bun, să trecem la cod unde totul va fi mult mai clar . Următoarea bucată de cod exemplifică cei 6 pași de mai sus, adică toată căutarea binară pentru acest exemplu. 

 

bool binary_search(int *a, int p, int q, int k) {
    if (p>q)
        return false;
    int m=(p+q)/2;
    if(a[m] == k)
        return true;
    if(a[m] > k)
        return binary_search(a, p, m, k);
    else
        return binary_search(a, p, m+1, k);
    return false;
}

Următorul exemplu funcționează corect aplicând acestă funcție:

 

    int numbers[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int to_be_found[] = {20, 5, 7, 13};
    bool expected[] = {false, true, true, false};

 

 

[TLG George]

Topic inactiv. Closed.