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