🔍

Vreau sa gasesc un element!

Dupa aceasta lectie, vei sti sa cauti un element intr-un tablou si sa afli daca exista sau nu.

INCEARCA

Gandeste-te la asta!

Provocarea ta:

Ai o lista de note: 8, 5, 10, 7, 9, 6

Cum ai verifica daca nota 10 exista in lista?

Dar daca lista ar avea 1000 de note?

Gandeste: Ce pasi ai urma pentru a gasi o valoare?

Click pentru indiciu

Ai compara valoarea cautata cu fiecare element, pe rand:

8 = 10? Nu. 5 = 10? Nu. 10 = 10? DA! Gasit!

INVATA

Algoritmul de cautare liniara

Cautarea liniara (Linear Search)

Cautarea liniara este cel mai simplu algoritm de cautare: verificam fiecare element, pe rand, pana gasim ce cautam sau pana terminam lista.

Se numeste "liniara" pentru ca parcurgem elementele in linie, unul dupa altul.

Cand o folosim? Cand tabloul NU este sortat si vrem sa gasim un element.

Pasii algoritmului

1

Porneste de la primul element (index 0)

2

Compara elementul curent cu valoarea cautata

3

Daca sunt egale: GASIT! Retine pozitia

4

Daca nu: treci la urmatorul element

5

Repeta pana gasesti sau termini tabloul

Demo interactiv: Cauta un numar

8 [0]

5 [1]

10 [2]

7 [3]

9 [4]

6 [5]

Cauta valoarea:

Codul pentru cautare liniara

int note[6] = {8, 5, 10, 7, 9, 6};
int n = 6;
int cautat = 10;  // valoarea pe care o cautam
int pozitie = -1;  // -1 inseamna "nu am gasit inca"

for(int i = 0; i < n; i++) {
    if(note[i] == cautat) {
        pozitie = i;  // Am gasit! Retin pozitia
        break;       // Ies din bucla
    }
}

if(pozitie != -1) {
    cout << "Gasit la pozitia " << pozitie;
} else {
    cout << "Nu exista in tablou";
}
                    

Varianta cu variabila "gasit"

bool gasit = false;  // flag - indicator

for(int i = 0; i < n; i++) {
    if(note[i] == cautat) {
        gasit = true;
        cout << "Gasit la pozitia " << i << endl;
        break;
    }
}

if(!gasit) {
    cout << "Valoarea nu exista in tablou" << endl;
}
                    

Bonus: Numarare aparitii

// Cate note de 10 sunt?
int contor = 0;

for(int i = 0; i < n; i++) {
    if(note[i] == 10) {
        contor++;  // numaram fiecare aparitie
    }
}

cout << "Sunt " << contor << " note de 10";
                    

Exemplu complet

#include <iostream>
using namespace std;

int main() {
    int note[100];
    int n, cautat;

    cout << "Cate note? ";
    cin >> n;

    for(int i = 0; i < n; i++) {
        cout << "Nota " << i + 1 << ": ";
        cin >> note[i];
    }

    cout << "Ce nota cauti? ";
    cin >> cautat;

    bool gasit = false;
    for(int i = 0; i < n; i++) {
        if(note[i] == cautat) {
            cout << "Nota " << cautat << " gasita la pozitia " << i << endl;
            gasit = true;
        }
    }

    if(!gasit) {
        cout << "Nota " << cautat << " nu exista." << endl;
    }

    return 0;
}
                    

VERIFICA

Hai sa vedem ce ai retinut!

1. Ce valoare are "pozitie" daca elementul cautat nu exista in tablou?

0

-1 (sau ramane neschimbat)

n

2. In tabloul {3, 7, 2, 9, 5}, la ce pozitie se afla valoarea 9?

4

3

9

3. Ce face instructiunea "break" in cautarea liniara?

Opreste bucla cand gaseste elementul

Sterge elementul gasit

Reporneste cautarea de la inceput

4. Pentru a numara de cate ori apare o valoare, folosim:

break si return

o variabila contor si nu folosim break

doua bucle for imbricate

🎉

Felicitari!

Ai terminat Lectia 3: Cautarea in tablouri

+50 XP

Acum stii sa cauti elemente in tablouri folosind cautarea liniara!

Continua la Lectia 4