CĂUTARE BINARĂ
Un CAZ PARTICULAR de probleme de tip « Divide et Impera » îl constituie căutarea binară: Se consideră un vector ordonat crescator cu N elemente şi o valoare K. Se cere să se scrie o funcţie care returnează poziţia elementului K (dacă există!)în vectorul dat. În cazul în care K nu există în vector, se returnează -1. O soluţie ar fi căutarea secvenţială: se parcurge vectorul în mod normal, şi se localizează elementul K. Această soluţie are complexitatea O(N). Metoda optimă de rezolvare este cautarea binară. Aceasta se foloseşte de metoda divide et impera. Se împarte vectorul în jumătate, după care se continuă căutarea, în mod similar, în acea parte a vectorului unde se afla elementul K. Condiţia ca vectorul să fie sortat este esenţială. Complexitatea acestui algoritm este O(logN) = "Visul programatorului".
EXEMPLU DE PROBLEMĂ REZOLVATĂ PRIN CĂUTARE BINARĂ
Căutarea unei valori date într-un vector ordonat
Programul de mai jos caută valoarea k în vectorul ordonat v[k], stocat în fişierul extern “vectOrd.in”:
Presupunând că fişierul extern “vectOrd.in” are conţinutul:
27
3 11 27 32 35 37 44 45 46 54 61 63 71 73 77 76 78 81 82 85 88 89 90 92 95 96 99
căutarea valorii 32 are ca efect :
iar căutarea valorii 33 are ca efect :
O variantă on-line poate fi experimentată la 
STUDIU DE CAZ
Până acum, ne-am ocupat mai mult de găsirea unui algoritm pentru a rezolva problemele pe care ni le-am propus (sau pe care ni le-au propus alţii …), fără a ne preocupa, în majoritatea cazurilor, de eficienţa acestor algoritmi. Situaţia este normală, la început, căci, pentru a îmbunătăţi un lucru, trebuie să ai ce îmbunătăţi!
În aplicaţiile reale, se pune adesea problema “ameliorării” soluţiilor găsite. Fără a încerca o abordare exhaustivă, să discutăm un caz concret:
Într-un fişier de pe disc, se găsesc două secvenţe de numere, ambele strict crescătoare. Astfel, pe prima linie se găsesc două numere naturale, n şi m, reprezentând respectiv numărul de valori din secvenţa a şi din secvenţa b. Pe linia a doua se găsesc n valori naturale, în ordine strict crescătoare, care constituie secvenţa a, iar pe a treia linie m valori naturale, în ordine strict crescătoare, care constituie secvenţa b. Se cere să se afişeze eventualele valori comune din cele două secvenţe şi numărul acestora.
În Exemplul de mai jos, secvenţa a este constituită din 32 de valori, iar secvenţa b din 30 de valori.
32 30
4 11 27 33 42 53 57 65 81 92 108 121 175 198 204 236 275 299 313 350 491 503 507 508 512 519 606 610 611 615 702 717
8 12 16 22 28 31 36 49 57 88 100 108 203 275 300 313 314 317 322 383 391 412 453 491 493 496 503 506 519 729
Se observă că valorile 57, 108, 275, 313, 491, 503 şi 519 se regăsesc în ambele secvenţe.
Algoritmul de mai jos abordează “prin forţă brută” problema: se citesc din fişier valorile n şi m, reprezentând lungimile celor două secvenţe, apoi cele două secvenţe sunt salvate în vectorii a[ ] şi b[ ]. Cu un dublu for, fiecare element din vectorul b[ ] (primul for) este căutat în vectorul a[ ] (al doilea for).
Programul ar putea arăta aşa:
iar rezultatul (corect!) al rulării ar fi:
O variantă on-line poate fi experimentată la 
Prima posibilitate de “îmbunătăţire” are în vedere consumul de memorie RAM (să nu uităm că, în practică, secvenţele ar putea fi foarte lungi, conducând la consum exagerat de memorie): este oare strict necesar să reţinem ambele secvenţe în vectori? Se observă imediat că, datorită căutării repetate în secvenţa a, aceasta trebuie reţinută într-un vector, pentru a evita citirea repetată din fişier a acestei secvenţe (lucru prohibitiv, care ar anula orice efort de ameliorare a algoritmului). Un număr din a doua secvenţă, însă, nu ne este de folos decât pe parcursul căutării lui în prima secvenţă, ceea ce înseamnă că, după citirea lui şi căutarea în prima secvenţă, poate fi “abandonat”, nemaifiind necesară reţinerea sa într-un vector. Am înlocuit astfe un întreg vector ( b[ ] ) cu o singură variabilă (b)! (Întrebare: puteam renunţa la a memora vectorul a[ ] , în locul lui memorând, în schimb, vectorul b[ ] ?)
Programul ar putea arăta aşa:
Rulând acest program, se obţine rezultatul de mai jos:
O variantă on-line poate fi experimentată la 
Au fost, în mod evident, necesare 32 x 30 = 960 de comparaţii între elemente.
N-am ţinut însă nicăieri seama, până acum, că cele două secvenţe sunt ambele strict crescătoare, reluând mereu de pe prima poziţe căutarea în secvenţa a, pentru fiecare nouă valoare b, când este clar că, dacă am găsit o “potrivire” pe o poziţie oarecare poz din vectorul a[ ], o alta nu poate să mai fie găsită decât pe o poziţie ulterioară. Este, deci, suficient să reţinem, de fiecare dată, poziţia ultimei “potriviri” şi să pornim căutarea următoare de la această poziţie mai departe.
Programul ar putea arăta acum aşa:
Rulând acest program, se obţine rezultatul de mai jos:
O variantă on-line poate fi experimentată la 
Observăm că n-a mai fost nevoie decât de 619 comparaţii!
Dar, tocmai am aflat în acest capitol că, în cazul vectorilor ordonaţi, avem o “armă” de căutare mult mai eficientă (de fapt, cea mai eficientă, care lucrează în O[ln n] ): căutarea binară. Aşa că s-o folosim!
Rulând programul (ce cuprinde subprogramul recursiv cautbin), se obţine rezultatul de mai jos:
O variantă on-line poate fi experimentată la 
A mai fost nevoie doar de 149 de comparaţii.
După cum se ştie, căutarea binară este cea mai rapidă metodă, având complexitatea O[ln n].
Mai putem spera la o îmbunătăţire? Putem perfecţiona perfecţiunea?
Răspunsul este … DA!
Combinând căutarea binară cu “perfecţionarea” de a porni căutarea de la poziţia ultimei “potriviri”, programul devine:
Rulând acest program (ultimul din această discuţie!), se obţine rezultatul de mai jos:
A mai fost nevoie doar de 130 de comparaţii.
Ţineţi cont că am pornit de la doi vectori şi 960 de comparaţii!
O variantă on-line poate fi experimentată la 