Căutarea liniară și binară în vectori C++

Căutarea răspunde la întrebarea „unde apare valoarea cerută?”. Înainte să scrii algoritmul, stabilește ce rezultat vrei: existența valorii, primul indice sau toate aparițiile. Aceste cerințe nu sunt echivalente atunci când vectorul conține valori repetate.

Ai nevoie de declararea și parcurgerea vectorilor. Folosim indici de la zero și rezultatul -1 când valoarea lipsește. Acesta este un semnal, nu un indice pe care îl poți accesa.

Căutarea liniară: verifici pe rând

Citim n și valoarea căutată x, apoi cele n elemente. Presupunem 0 <= n <= 100000, iar valorile și x sunt între -1000000000 și 1000000000.

Varianta cu tablou clasic

Tabloul a[100000] are capacitate fixă. Datele ocupă doar primele n poziții, iar indicii folosiți sunt de la 0 la n - 1. Limita lui n trebuie să respecte această capacitate.

#include <iostream>

int main() {
    int n = 0, x = 0;
    std::cin >> n >> x;
    int a[100000]{};
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    int pozitie = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i] == x) {
            pozitie = i;
            break;
        }
    }
    std::cout << pozitie << '\n';
    return 0;
}

Varianta cu std::vector

std::vector<int> a(n) creează exact n elemente. Citirea, accesul a[i] și algoritmul rămân aceleași; se schimbă declararea și modul de gestionare a dimensiunii.

#include <iostream>
#include <vector>

int main() {
    int n = 0, x = 0;
    std::cin >> n >> x;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    int pozitie = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i] == x) {
            pozitie = i;
            break;
        }
    }
    std::cout << pozitie << '\n';
    return 0;
}

Pentru n = 4, x = 2 și vectorul 7 2 9 2, rezultatul este 1. Verificăm 7, apoi 2 și ne oprim. Instrucțiunea break încheie bucla în care se află. Apariția de la indicele 3 nu mai este examinată, pentru că am găsit deja prima apariție.

Căutarea liniară se oprește la prima potrivire, chiar dacă valoarea mai apare.Redă animațiaO singură rulare · 6 secunde

Dacă elimini break, fiecare potrivire suprascrie pozitie, iar la final obții ultimul indice. Dacă vrei numărul aparițiilor, ai nevoie de un contor și trebuie să parcurgi întregul vector. Pentru un vector gol nu intrăm în buclă și păstrăm -1.

Căutarea binară cere date sortate

Dacă elementele sunt deja ordonate crescător, inclusiv cu egalități, putem elimina la fiecare pas aproximativ jumătate din interval. Comparăm valoarea din mijloc cu x. O valoare prea mică ne spune că nici elementele din stânga ei nu pot fi soluția.

Programul următor găsește tot prima apariție. Are aceleași limite de intrare, dar cere suplimentar ca vectorul să fie sortat. Păstrăm intervalul [stanga, dreapta): capătul stâng este inclus, cel drept este exclus.

Varianta cu tablou clasic

Tabloul a[100000] are capacitate fixă. Datele ocupă doar primele n poziții, iar indicii folosiți sunt de la 0 la n - 1. Limita lui n trebuie să respecte această capacitate.

#include <iostream>

int main() {
    int n = 0, x = 0;
    std::cin >> n >> x;
    int a[100000]{};
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    int stanga = 0, dreapta = n;
    while (stanga < dreapta) {
        int mijloc = stanga + (dreapta - stanga) / 2;
        if (a[mijloc] < x) {
            stanga = mijloc + 1;
        } else {
            dreapta = mijloc;
        }
    }
    int pozitie = -1;
    if (stanga < n && a[stanga] == x) {
        pozitie = stanga;
    }
    std::cout << pozitie << '\n';
    return 0;
}

Varianta cu std::vector

std::vector<int> a(n) creează exact n elemente. Citirea, accesul a[i] și algoritmul rămân aceleași; se schimbă declararea și modul de gestionare a dimensiunii.

#include <iostream>
#include <vector>

int main() {
    int n = 0, x = 0;
    std::cin >> n >> x;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    int stanga = 0, dreapta = n;
    while (stanga < dreapta) {
        int mijloc = stanga + (dreapta - stanga) / 2;
        if (a[mijloc] < x) {
            stanga = mijloc + 1;
        } else {
            dreapta = mijloc;
        }
    }
    int pozitie = -1;
    if (stanga < n && a[stanga] == x) {
        pozitie = stanga;
    }
    std::cout << pozitie << '\n';
    return 0;
}

Pentru 1 2 2 4 7 și x = 2, intervalele sunt [0, 5), [0, 2), [0, 1), apoi [1, 1). Mijloacele examinate sunt 2, 1, 0. Când intervalul devine gol, stanga este primul loc unde valoarea ar putea fi cel puțin x; verificarea finală confirmă dacă este chiar egală.

La egalitate nu ne oprim imediat, deoarece ar putea exista o apariție mai devreme. Micșorăm capătul drept. Condiția stanga < n protejează accesul final când x depășește toate elementele. Operatorul && nu mai evaluează accesul dacă această condiție este falsă.

Alegerea metodei și greșeli frecvente

Căutarea liniară funcționează și pe date nesortate și face cel mult n comparații, deci are timp O(n). Căutarea binară examinează O(log n) elemente pentru n > 0. Ambele folosesc doar câteva variabile suplimentare, pe lângă vectorul memorat.

Nu sorta automat datele doar ca să poți căuta binar: sortarea are un cost și schimbă indicii originali. Pentru multe căutări în aceeași colecție sortată, căutarea binară devine deosebit de utilă. Pentru o singură căutare într-un vector nesortat, parcurgerea liniară este adesea alegerea directă.

În variantele clasice, memoria rezervată este dată de capacitatea din declarație, nu de numărul de elemente folosite. În variantele cu std::vector, stocarea din aceste exemple este proporțională cu dimensiunile citite. Algoritmul și numărul de elemente prelucrate nu se schimbă între reprezentări. Inițializarea cu {} a tabloului clasic pune la zero întreaga capacitate, inclusiv pozițiile nefolosite; acest cost este separat de parcurgerea celor n elemente sau a celor n * m celule.

Exersează

1. Ce întoarce căutarea liniară pentru 5 5 5 și x = 5?
2. Ce rezultat obții dacă x lipsește?
3. De ce condiția finală nu citește a[n]?
4. Cum transformi indicele găsit într-o poziție numerotată de la unu?

Răspunsuri: 0; -1; testul stanga < n oprește evaluarea accesului; adaugi unu numai dacă rezultatul nu este -1. Pentru cazul absent păstrezi semnalul stabilit de enunț.

Continuă cu sortarea vectorilor.