Căutarea binară la BAC: intervale și prima apariție

Căutarea binară găsește o valoare într-un vector ordonat reducând repetat intervalul în care ea ar putea exista. Compari valoarea căutată cu elementul din mijloc și elimini jumătatea care nu poate conține răspunsul. La BAC, corectitudinea depinde de ordonarea datelor și de actualizarea strictă a limitelor.

Vom folosi un vector ordonat crescător, cu egalități permise, și indici de la zero. Programul va găsi prima apariție a unei valori, nu o apariție oarecare. Această precizare este necesară atunci când datele conțin duplicate, situație pe care merită să o verifici și în problemele de BAC.

De ce vectorul trebuie să fie ordonat

Dacă elementul din mijloc este mai mic decât valoarea căutată, toate elementele din stânga lui sunt cel mult egale cu el. Prin urmare, niciunul nu poate fi valoarea căutată. Putem elimina acea parte fără să pierdem un răspuns posibil.

Acest raționament folosește ordinea. Într-un vector neordonat, o valoare mai mare poate fi oriunde, inclusiv în stânga mijlocului. Eliminarea unei jumătăți nu ar mai fi justificată.

De exemplu, în secvența nouă, unu, șapte, trei, cinci, comparația cu mijlocul nu spune pe ce parte se află nouă. Aplicarea căutării binare direct pe asemenea date poate rata o valoare prezentă. Faptul că programul nu dă eroare la rulare nu înseamnă că metoda este aplicabilă.

Intervalul închis de căutare

Păstrăm două limite: indicele din stânga și indicele din dreapta. Ambele sunt incluse în intervalul analizat. Inițial, intervalul acoperă întregul vector: de la zero până la lungime minus unu.

Cât timp limita stângă este cel mult egală cu limita dreaptă, există cel puțin o poziție de verificat. Când limita stângă devine mai mare, intervalul este gol. Aceasta este condiția de oprire, nu o poziție pe care să o accesezi.

Mijlocul poate fi calculat adunând la limita stângă jumătate din diferența dintre limite. Această formă evită adunarea directă a două limite mari. Pentru intervalele mici din exemplul nostru, ambele calcule ar încăpea, dar forma prin diferență exprimă aceeași idee fără acel risc suplimentar.

Exemplu cu valoare repetată

Vectorul este doi, patru, patru, patru, șapte, nouă, doisprezece. Căutăm prima apariție a lui patru. Primul mijloc este indicele trei, unde găsim patru, dar acesta nu este neapărat primul.

Stânga	Dreapta	Mijloc	Valoare	Decizie
0	6	3	4	Reținem 3 și căutăm mai la stânga
0	2	1	4	Reținem 1 și căutăm mai la stânga
0	0	0	2	Eliminăm poziția 0

La final, intervalul este gol, iar cel mai bun indice reținut este unu. În numerotarea pozițiilor de la unu, răspunsul este poziția a doua. Programul nostru afișează indicele, deci va afișa unu.

Dacă ai opri algoritmul la prima egalitate, ai obține indicele trei. Acesta este un răspuns corect numai pentru cerința „găsește o apariție”, nu pentru cerința despre prima apariție.

Program C++ complet

Programul citește între zero și o mie de elemente deja ordonate crescător, apoi valoarea căutată. Afișează primul indice la care aceasta apare sau minus unu dacă lipsește.

#include <iostream>
using namespace std;

int main() {
    int n, v[1000], x;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> v[i];
    cin >> x;
    int st = 0, dr = n - 1, rezultat = -1;
    while (st <= dr) {
        int mij = st + (dr - st) / 2;
        if (v[mij] < x) {
            st = mij + 1;
        } else {
            if (v[mij] == x) rezultat = mij;
            dr = mij - 1;
        }
    }
    cout << rezultat;
    return 0;
}

Când valoarea din mijloc este mai mare decât cea căutată, căutăm în stânga. Când este egală, salvăm candidatul și tot în stânga continuăm, pentru a verifica dacă există o apariție mai timpurie. Cele două situații au aceeași actualizare a limitei drepte, dar numai egalitatea schimbă rezultatul.

Pentru un vector vid, limita dreaptă este minus unu, iar bucla nu începe. Rezultatul rămâne minus unu. Nu se accesează nicio celulă, ceea ce face cazul-limită sigur în domeniul declarat.

De ce limitele exclud mijlocul

După comparație, poziția din mijloc a fost deja analizată. În varianta cu interval închis, noua limită trebuie să treacă de ea: fie stânga devine mijloc plus unu, fie dreapta devine mijloc minus unu.

Dacă ai pune doar stânga egală cu mijlocul, un interval cu două elemente poate rămâne neschimbat. Calculul întreg al mijlocului poate produce aceeași poziție la fiecare pas, iar bucla nu se mai termină.

Există și variante corecte cu intervale semiînchise și alte convenții. Nu combina însă condiția de oprire dintr-o variantă cu actualizările alteia. Alege o singură reprezentare a intervalului și justifică toate limitele în acea convenție.

Prima și ultima apariție

Pentru ultima apariție, la egalitate salvezi indicele și continui în dreapta. Celelalte comparații elimină în continuare partea imposibilă. Astfel, cauți un candidat cu indice mai mare decât cel deja găsit.

Dacă ai aflat prima și ultima apariție, numărul aparițiilor este diferența dintre indicii lor plus unu. Această formulă se aplică numai când valoarea există. Dacă prima căutare întoarce minus unu, numărul aparițiilor este zero și nu folosești formula pe două rezultate de absență.

Ordonarea garantează că toate aparițiile egale sunt consecutive. Fără această proprietate, diferența dintre prima și ultima poziție ar include și alte valori. Acesta este încă un loc în care condiția inițială a metodei este esențială.

Cât de eficientă este căutarea

La fiecare pas, intervalul posibil se reduce aproximativ la jumătate. Numărul comparațiilor crește logaritmic cu lungimea vectorului. Pentru un vector cu o mie de elemente, sunt necesare doar aproximativ zece etape de înjumătățire, nu o mie de verificări consecutive.

Această estimare privește căutarea într-un vector deja ordonat. Dacă trebuie să sortezi mai întâi datele pentru o singură căutare, costul sortării poate domina. Pentru multe căutări pe aceleași date, ordonarea inițială poate fi justificată.

În programul prezentat, citirea tuturor elementelor rămâne liniară. Când descrii eficiența, precizează dacă analizezi doar căutarea sau întregul program cu citire. Această separare evită explicațiile aparent contradictorii și susține înțelegerea complexității.

Exerciții cu răspunsuri explicate

În vectorul unu, trei, cinci, șapte, caută cinci. Primul mijloc, în convenția programului, este indicele unu, cu valoarea trei. Căutarea continuă în dreapta și găsește indicele doi.

În același vector, caută șase. După eliminări succesive, intervalul devine gol fără egalitate. Rezultatul este minus unu, nu indicele elementului cel mai apropiat.

În vectorul patru, patru, patru, caută prima apariție a lui patru. Rezultatul este indicele zero. Oprirea la prima egalitate ar putea returna indicele unu și ar rata cerința.

Caută o valoare mai mică decât minimul. Limita dreaptă se deplasează către stânga până când intervalul devine gol. Cazul nu cere accesarea unei poziții negative.

Întrebări frecvente

Pot folosi căutarea binară pe un vector descrescător?

Da, dar sensul comparațiilor care aleg jumătatea trebuie adaptat. Programul de aici presupune ordine crescătoare și nu trebuie aplicat neschimbat unui vector descrescător.

Rezultatul minus unu poate fi o valoare validă din vector?

Da, vectorul poate conține valoarea minus unu. Rezultatul programului este însă un indice, iar indicii valizi sunt nenegativi. De aceea, minus unu poate semnala absența fără ambiguitate.

Ce teste să folosesc?

Verifică un singur element, absența, prima și ultima valoare, duplicate și vectorul vid. Pentru a corecta limitele unei bucle proprii, poți urmări intervalele la meditații de informatică.