Împărțirea problemei — unde tai la mijloc

Cum împarți un interval [st, dr]

Lucrezi mai tot timpul cu un interval de indici [st, dr] — de la st (stânga) până la dr (dreapta), ambele incluse. Pe el vrei să-l spargi în subprobleme mai mici, ca să le rezolvi separat.

De obicei tai la mijloc, în două jumătăți. De ce la mijloc și nu, să zicem, după primul element? Pentru că tăietura la mijloc face fiecare bucată de aproximativ jumătate din dimensiune. Așa, după fiecare pas problema se înjumătățește, iar numărul de pași până ajungi la bucăți minuscule e mic (de ordinul log din mărime). Dacă ai tăia mereu doar un element, ai face tot atâția pași câte elemente — adică nimic câștigat față de o parcurgere obișnuită.

Uneori spargi în mai multe părți (de exemplu în trei, la unele probleme), dar ideea rămâne aceeași: împarți intervalul în bucăți disjuncte care, puse la loc, acoperă exact intervalul de pornire. Aici ne concentrăm pe cazul clasic: două jumătăți.

Calculul mijlocului: mid = st + (dr - st) / 2

Mijlocul pare banal: mid = (st + dr) / 2. Matematic e corect. Dar în cod ascunde o capcană. st și dr sunt numere întregi pe un tip cu limită (în C++, int ține valori până la aproximativ două miliarde). Dacă lucrezi cu indici mari și st plus dr depășesc împreună acea limită, suma face overflow: rezultatul „se rotește" și devine un număr negativ greșit. Mijlocul iese aberant, iar algoritmul se strică.

Soluția este să rescrii formula astfel încât să nu aduni două numere mari:

mid = st + (dr - st) / 2

Aici dr - st este lungimea intervalului minus unu — un număr mic, cât bucata curentă, niciodată cât suma celor doi indici. Îl împarți la 2 și îl adaugi peste st. Rezultatul e exact același mijloc, dar fără riscul de a depăși limita tipului. E o rescriere pe care merită să o folosești mereu, din reflex.

Exemplu pas cu pas

Să luăm intervalul [0, 7] (opt elemente, de la indicele 0 la 7). Calculăm:

mid = 0 + (7 - 0) / 2 = 0 + 3 = 3

Deci mid = 3. Tăiem fix după indicele 3. Rezultă două jumătăți:

• jumătatea stângă: [st, mid] = [0, 3] (indicii 0, 1, 2, 3)
• jumătatea dreaptă: [mid + 1, dr] = [4, 7] (indicii 4, 5, 6, 7)

Observă: indicele 3 intră doar în stânga, iar 4 deschide dreapta. Niciun indice nu apare în ambele și niciunul nu lipsește. Puse cap la cap, [0, 3] și [4, 7] acoperă din nou exact [0, 7].

Dacă mai tai o dată stânga [0, 3]: mid = 0 + (3 - 0) / 2 = 1, deci [0, 1] și [2, 3]. Vezi cum fiecare tăietură produce bucăți tot mai mici, până rămâi cu intervale de un singur element.

Implementare C++

Funcția de mai jos doar împarte intervalul și afișează jumătățile, ca să izolezi pasul de tăiere. Nu rezolvă nimic altceva — combinarea rezultatelor e subiectul altei lecții.

#include <iostream>
using namespace std;

// imparte [st, dr] in jumatati si afiseaza intervalele rezultate
void imparte(int st, int dr) {
    if (st >= dr) {            // un singur element sau interval gol: oprire
        cout << "frunza [" << st << ", " << dr << "]\n";
        return;
    }
    int mid = st + (dr - st) / 2;   // mijloc fara risc de overflow
    cout << "tai [" << st << ", " << dr << "] -> ";
    cout << "[" << st << ", " << mid << "] si ";
    cout << "[" << (mid + 1) << ", " << dr << "]\n";
    imparte(st, mid);          // jumatatea stanga: contine mid
    imparte(mid + 1, dr);      // jumatatea dreapta: incepe dupa mid
}

int main() {
    imparte(0, 7);             // imparte un interval de 8 elemente
    return 0;
}

Rulând, vezi cum [0, 7] se sparge în [0, 3] și [4, 7], apoi fiecare se sparge mai departe, până la frunze (intervale de un singur element). Tot programul nu face decât tăietura corectă, repetat.

Recapitulare

• Tai intervalul [st, dr] de obicei la mijloc, ca fiecare bucată să fie de aproximativ jumătate și problema să se micșoreze repede.
• Calculează mijlocul cu mid = st + (dr - st) / 2 — dă același rezultat ca (st + dr) / 2, dar fără riscul de overflow la indici mari.
• Împarte corect în [st, mid] și [mid + 1, dr]: fără suprapunere, fără element pierdut, iar st == dr este oprire, nu o tăietură nouă.