Metode de căutare: secvențială, binară

În lumea informaticii, căutarea reprezintă o operațiune esențială în rezolvarea problemelor și găsirea informațiilor dorite. Există diferite metode de căutare, fiecare având avantajele și dezavantajele sale. În această lecție, vom explora două dintre cele mai comune metode de căutare: căutarea secvențială și căutarea binară.

Căutarea secvențială

Căutarea secvențială este cea mai simplă și directă metodă de căutare. Aceasta constă în parcurgerea elementelor unei liste în ordine, până când se găsește elementul căutat sau se ajunge la sfârșitul listei. Dacă elementul este găsit, căutarea se încheie și se returnează poziția acestuia în listă.

Avantajul căutării secvențiale constă în simplitatea sa. Este ușor de implementat și poate fi folosită în cazul listelor de dimensiuni mici sau în cazurile în care lista nu este sortată. Totuși, această metodă are o complexitate liniară, ceea ce înseamnă că timpul de căutare crește odată cu mărimea listei.

#include <iostream>

int cautareSecventiala(int lista[], int lungime, int elementCautat) {
    for (int i = 0; i < lungime; i++) {
        if (lista[i] == elementCautat) {
            return i;  // Elementul a fost găsit, returnăm poziția sa în tablou
        }
    }

    return -1; // Elementul nu a fost găsit în tablou
}

int main() {
    int lungime; // Introducerea dimensiunii listei
    std::cout << "Introduceti lungimea listei: ";
    std::cin >> lungime;

    int lista[lungime];

    // Introducerea elementelor listei
    std::cout << "Introduceti elementele listei:\n";
    for (int i = 0; i < lungime; i++) {
        std::cout << "Element " << i + 1 << ": ";
        std::cin >> lista[i];
    }

    int elementCautat;
    std::cout << "Introduceti elementul cautat: ";
    std::cin >> elementCautat;

    int pozitie = cautareSecventiala(lista, lungime, elementCautat);

    if (pozitie != -1) {
        std::cout << "Elementul " << elementCautat << " a fost gasit la pozitia " << pozitie << "." << std::endl;
    } else {
        std::cout << "Elementul " << elementCautat << " nu a fost gasit in lista." << std::endl;
    }

    return 0;
}

Această versiune utilizează un tablou static pentru a stoca elementele listei, evitând utilizarea de pointeri.

#include <iostream>

int cautareSecventiala(int lista[], int lungime, int elementCautat) {
    for (int i = 0; i < lungime; i++) {
        if (lista[i] == elementCautat) {
            return i;  // Elementul a fost găsit, returnăm poziția sa în tablou
        }
    }

    return -1; // Elementul nu a fost găsit în tablou
}

int main() {
    // Poți inițializa lista după nevoie
    // Exemplu: int lista[] = {3, 8, 1, 5, 7};

    int lungime; // Introducerea dimensiunii listei
    std::cout << "Introduceti lungimea listei: ";
    std::cin >> lungime;

    int* lista = new int[lungime];

    // Introducerea elementelor listei
    std::cout << "Introduceti elementele listei:\n";
    for (int i = 0; i < lungime; i++) {
        std::cout << "Element " << i + 1 << ": ";
        std::cin >> lista[i];
    }

    int elementCautat;
    std::cout << "Introduceti elementul cautat: ";
    std::cin >> elementCautat;

    int pozitie = cautareSecventiala(lista, lungime, elementCautat);

    if (pozitie != -1) {
        std::cout << "Elementul " << elementCautat << " a fost gasit la pozitia " << pozitie << "." << std::endl;
    } else {
        std::cout << "Elementul " << elementCautat << " nu a fost gasit in lista." << std::endl;
    }

    delete[] lista; // Eliberăm memoria alocată pentru lista

    return 0;
}

Acesta este un program simplu care permite utilizatorului să introducă lungimea listei și elementele acesteia, apoi să introducă elementul căutat. Programul utilizează funcția cautareSecventiala pentru a găsi elementul și pentru a afișa poziția sa în lista sau un mesaj de negăsire.

Căutarea binară

Căutarea binară este o metodă eficientă de căutare, în special în cazul listelor sortate. Aceasta constă în împărțirea repetată a listei în jumătăți și compararea elementului căutat cu elementul din mijlocul listei. Dacă elementul căutat este mai mic decât elementul din mijloc, căutarea continuă în jumătatea inferioară a listei. Dacă elementul căutat este mai mare decât elementul din mijloc, căutarea continuă în jumătatea superioară a listei. Acest proces se repetă până când elementul este găsit sau jumătatea de căutare devine vidă.

Avantajul căutării binare constă în eficiența sa. Deoarece lista este împărțită în jumătăți la fiecare pas, timpul de căutare este redus semnificativ. Complexitatea căutării binare este logaritmică, ceea ce înseamnă că timpul de căutare crește lent odată cu mărimea listei.

#include <iostream>

int cautareBinar(int lista[], int stanga, int dreapta, int elementCautat) {
    while (stanga <= dreapta) {
        int mijloc = stanga + (dreapta - stanga) / 2;

        if (lista[mijloc] == elementCautat) {
            return mijloc;  // Elementul a fost găsit, returnăm poziția sa în tablou
        } else if (lista[mijloc] < elementCautat) {
            stanga = mijloc + 1;  // Căutăm în partea dreaptă a mijlocului
        } else {
            dreapta = mijloc - 1;  // Căutăm în partea stângă a mijlocului
        }
    }

    return -1; // Elementul nu a fost găsit în tablou
}

int main() {
    // Inițializează lista sortată după nevoie
    // Exemplu: int lista[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};

    int lungime; // Introducerea dimensiunii listei
    std::cout << "Introduceti lungimea listei: ";
    std::cin >> lungime;

    int* lista = new int[lungime];

    // Introducerea elementelor listei (se presupune că lista este sortată)
    std::cout << "Introduceti elementele listei (sortate):\n";
    for (int i = 0; i < lungime; i++) {
        std::cout << "Element " << i + 1 << ": ";
        std::cin >> lista[i];
    }

    int elementCautat;
    std::cout << "Introduceti elementul cautat: ";
    std::cin >> elementCautat;

    int pozitie = cautareBinar(lista, 0, lungime - 1, elementCautat);

    if (pozitie != -1) {
        std::cout << "Elementul " << elementCautat << " a fost gasit la pozitia " << pozitie << "." << std::endl;
    } else {
        std::cout << "Elementul " << elementCautat << " nu a fost gasit in lista." << std::endl;
    }

    delete[] lista; // Eliberăm memoria alocată pentru lista

    return 0;
}

Acest program permite utilizatorului să introducă lungimea și elementele unei liste sortate și apoi caută un element specific utilizând căutarea binară. Programul afișează rezultatul căutării, indicând dacă elementul a fost găsit sau nu, împreună cu poziția sa în tablou.

Compararea căutării secvențiale și a căutării binare

Atunci când trebuie să alegem între căutarea secvențială și căutarea binară, trebuie să ținem cont de natura listei și de dimensiunea acesteia. Dacă lista este mică și/sau neordonată, căutarea secvențială poate fi o opțiune potrivită. Dacă lista este mare și/sau sortată, căutarea binară este preferată.

Este important de menționat că utilizarea căutării binare implică un cost suplimentar: lista trebuie să fie sortată în prealabil. Dacă lista se modifică frecvent, sortarea acesteia poate fi costisitoare în timp și resurse. În astfel de cazuri, căutarea secvențială poate fi o alternativă mai bună.

Concluzie

Căutarea este o operațiune esențială în informatică și există diferite metode de căutare, fiecare cu avantajele și dezavantajele sale. Căutarea secvențială este simplă și directă, dar poate fi ineficientă în cazul listelor mari. Căutarea binară este eficientă, dar necesită o listă sortată. Alegerea metodei potrivite depinde de natura și dimensiunea listei. În final, important este să găsim metoda de căutare care să se potrivească cel mai bine nevoilor noastre.