Invatare Atomica

Vreau sa gasesc un element intr-un tablou!

Progres lectie:
0%
🎯

Obiectivul lectiei

Ai o lista cu 1000 de numere de telefon. Cum gasesti rapid daca un anumit numar exista in lista? Verifici fiecare pe rand, sau exista o metoda mai rapida?

Dupa aceasta lectie vei putea:

  • Sa explici de ce conteaza cautarea
  • Sa evaluezi cautarea secventiala - verificam pe rand
  • Sa aplici cautare secventiala in C++
  • Sa numeri de cate ori apare o valoare
  • Sa gasesti primul element care indeplineste o conditie
  • ⭐ APROFUNDARE Sa aplici cautarea binara — algoritm de liceu/olimpiada, optional pentru cls. VIII

Incearca singur!

🎯 INCEARCA

Testeaza inainte sa inveti!

Nu trebuie sa intelegi totul acum. Doar copiaza, ruleaza si observa ce se intampla.

Misiunea ta (7 minute):
1
Copiaza codul de mai jos si lipeste-l pe OneCompiler. Apasa Run. Observa cum programul cauta numarul 4 in tablou.
#include <iostream> using namespace std; int main() { int x[7] = {3, 8, 1, 4, 9, 2, 7}; int cautat = 4; bool gasit = false; for (int i = 0; i < 7; i++) { cout << "Verific pozitia " << i << ": x[" << i << "] = " << x[i]; if (x[i] == cautat) { cout << " <-- GASIT!" << endl; gasit = true; break; } cout << endl; } if (!gasit) cout << "Numarul " << cautat << " NU exista in tablou." << endl; return 0; }
▶ Deschide OneCompiler
2
Schimba valoarea lui cautat in 5 (un numar care NU exista in tablou). Ruleaza din nou. Ce mesaj apare? Cate pozitii a verificat programul?
3
Schimba cautat in 3 (primul element). Cate verificari face acum? Dar daca pui 7 (ultimul element)?
4
Scoate linia cu break; (sterge-o sau pune // in fata). Ruleaza cu cautat = 4. Ce se schimba? De ce e important break?
5
Modifica tabloul in {1, 2, 3, 4, 5, 6, 7} (sortat crescator) si cauta 4. Numara cate verificari face. Tine minte acest numar - vom vedea cum cautarea binara face mai putine!
🌟 BONUS: Modifica programul sa numere de cate ori apare un numar in tablou. Foloseste tabloul {3, 1, 4, 1, 5, 1, 2} si cauta 1. Cate aparitii gaseste?
▶ Blocat la pasul 2? Click aici pentru un indiciu

Cu cautat = 5, programul verifica TOATE cele 7 pozitii fara sa gaseasca numarul 5.

La final, gasit ramane false si se afiseaza mesajul "NU exista in tablou".

Aceasta este situatia cea mai defavorabila: trebuie sa parcurgem tot tabloul.

▶ Blocat la pasul 4? Click aici

Fara break, chiar daca gasim elementul, bucla continua sa verifice TOATE pozitiile ramase.

Cu break, bucla se opreste imediat ce gasim elementul - economisim timp!

break inseamna "iesi din bucla acum". E ca si cum ai spune: "Am gasit ce cautam, nu mai caut."

▶ Blocat la BONUS? Click aici

In loc de bool gasit, foloseste int contor = 0;

In bucla, in loc de break, pune contor++; de fiecare data cand x[i] == cautat.

La final, afiseaza contor. Rezultat asteptat: 3 aparitii ale lui 1.

1

De ce conteaza cautarea?

De ce conteaza cautarea?

Cautarea este una dintre cele mai fundamentale operatii in programare. Aproape orice aplicatie are nevoie sa caute ceva:

• Scoala: Exista elevul "Popescu" in catalog? La ce pozitie?
• Magazin: Avem produsul cu codul 12345 in stoc?
• Jocuri: Exista scorul 9999 in top 100?
• Dictionar: Exista cuvantul "algoritm" in dictionar?

📖 Analogie: Cautarea in biblioteca

Imagineaza-ti ca esti intr-o biblioteca cu 10.000 de carti. Cauti o carte anume.

Metoda 1 (secventiala): Mergi raft cu raft, carte cu carte, pana o gasesti. Daca e ultima carte, verifici toate 10.000!

Metoda 2 (binara): Cartile sunt ordonate alfabetic. Te uiti la mijloc: "M". Cartea ta incepe cu "D", deci e in prima jumatate. Injumatatesti din nou. In maxim 14 pasi gasesti cartea din 10.000!

2

Cautarea secventiala - verificam pe rand

Cautarea secventiala - verificam pe rand

Cea mai simpla metoda de cautare: parcurgem tabloul element cu element, de la primul la ultimul, si verificam daca elementul curent este cel cautat.

Algoritmul are 3 pasi:

Pasul 1: Presupunem ca elementul nu exista (gasit = false).
Pasul 2: Parcurgem tabloul de la primul la ultimul element.
Pasul 3: Daca gasim elementul, marcam gasit = true si iesim din bucla cu break.

Algoritmul in pseudocod
// Cautare secventiala gasit ← false pentru i de la 0 pana la n-1: daca x[i] == cautat: gasit ← true opreste bucla
3

Cautare secventiala in C++

Cautare secventiala in C++

Sa vedem codul complet. Cautam valoarea 4 in tabloul {3, 8, 1, 4, 9, 2, 7}.

Cautare secventiala
int x[7] = {3, 8, 1, 4, 9, 2, 7}; int cautat = 4; bool gasit = false; int pozitie = -1; // -1 inseamna "negasit" for (int i = 0; i < 7; i++) { if (x[i] == cautat) { gasit = true; pozitie = i; break; // am gasit, nu mai cautam } } if (gasit) cout << "Gasit la pozitia " << pozitie << endl; // Gasit la pozitia 3 else cout << "Nu exista in tablou" << endl;
💡 De ce folosim break?

break opreste bucla imediat ce gasim elementul. Fara break, programul ar continua sa verifice TOATE elementele ramase - o munca inutila daca am gasit deja ce cautam!

4

Cautarea binara - DOAR in tablouri sortate! ⭐ APROFUNDARE / OPTIONAL

Cautarea binara - DOAR in tablouri sortate! ⭐ APROFUNDARE / OPTIONAL
⚠ Continut extracurricular — dincolo de programa cls. VIII (OMEN 3393/2017)

Cautarea binara este un algoritm studiat in liceu si la olimpiade. Nu este ceruta la evaluarile nationale de clasa a VIII-a. Parcurge-o daca esti curios sau pregatesti olimpiada — altfel, sarite la atomul 5 este perfect OK!

Daca tabloul este sortat (crescator), putem folosi o metoda mult mai rapida: cautarea binara. In loc sa verificam fiecare element, injumatatim zona de cautare la fiecare pas.

Ideea: Ne uitam la elementul din mijloc:

• Daca e cel cautat → GASIT!
• Daca cel cautat e mai mic → cautam in jumatatea stanga
• Daca cel cautat e mai mare → cautam in jumatatea dreapta

📖 Analogie: Ghiceste numarul!

Prietenul tau s-a gandit la un numar intre 1 si 100. La fiecare incercare, iti spune "mai mare" sau "mai mic".

Strategia optima: intrebi mereu mijlocul. "Este 50?" - "Mai mare." - "Este 75?" - "Mai mic." - "Este 62?" In maxim 7 incercari ghicesti din 100 de numere!

Cautare binara in C++
int x[8] = {2, 5, 8, 12, 15, 23, 37, 45}; // SORTAT! int n = 8, cautat = 15; int st = 0, dr = n - 1; // limitele zonei de cautare bool gasit = false; int pozitie = -1; while (st <= dr) { int mij = (st + dr) / 2; // calculam mijlocul if (x[mij] == cautat) { gasit = true; pozitie = mij; break; } else if (cautat < x[mij]) dr = mij - 1; // cautam in jumatatea stanga else st = mij + 1; // cautam in jumatatea dreapta } if (gasit) cout << "Gasit la pozitia " << pozitie << endl; // Gasit la pozitia 4 else cout << "Nu exista in tablou" << endl;
5

De cate ori apare o valoare?

De cate ori apare o valoare?

Uneori nu vrem doar sa stim daca exista un element, ci de cate ori apare. De exemplu: de cate ori a luat un elev nota 10?

Diferenta fata de cautarea simpla: nu folosim break, pentru ca trebuie sa verificam TOATE elementele. Folosim un contor pe care il incrementam la fiecare aparitie.

Numarare aparitii
int note[8] = {7, 10, 8, 10, 6, 10, 9, 10}; int cautat = 10; int contor = 0; // numaram aparitiile for (int i = 0; i < 8; i++) { if (note[i] == cautat) { contor++; // am gasit inca o aparitie } } cout << "Nota " << cautat << " apare de " << contor << " ori" << endl; // Nota 10 apare de 4 ori
💡 De ce NU folosim break aici?

La cautare simpla, break opreste bucla dupa prima gasire. Dar la numarare, trebuie sa verificam toate elementele pentru ca valoarea poate aparea de mai multe ori. Daca am pune break, am numara mereu maximum 1 aparitie!

6

Gaseste primul element care indeplineste o conditie

Gaseste primul element care indeplineste o conditie

Nu cautam mereu o valoare exacta. Uneori vrem sa gasim primul element care satisface o conditie: primul numar par, prima nota peste 8, primul numar negativ, etc.

Structura e similara cu cautarea secventiala, dar in loc de x[i] == cautat, punem conditia noastra.

Primul numar par din tablou
int x[6] = {7, 3, 9, 4, 8, 1}; int pozitie = -1; // -1 = nu am gasit inca for (int i = 0; i < 6; i++) { if (x[i] % 2 == 0) { // conditia: este par? pozitie = i; break; // am gasit primul, ne oprim } } if (pozitie != -1) cout << "Primul par: " << x[pozitie] << " la pozitia " << pozitie << endl; // 4 la pozitia 3 else cout << "Nu exista numere pare" << endl;
🔑 Sablon general: cautare cu conditie

Poti inlocui conditia x[i] % 2 == 0 cu orice alta conditie:
• Prima nota peste 8: x[i] > 8
• Primul numar negativ: x[i] < 0
• Primul multiplu de 5: x[i] % 5 == 0
• Prima cifra de doua cifre: x[i] >= 10 && x[i] <= 99

7

Cautare secventiala + numarare + cautare cu conditie

Cautare secventiala + numarare + cautare cu conditie

Acum punem totul impreuna intr-un program complet care citeste un tablou, cauta o valoare, numara aparitiile si gaseste primul numar par.

Program complet - ruleaza-l!
#include <iostream> using namespace std; int main() { int n; cout << "Cate elemente are tabloul? "; cin >> n; int x[100]; for (int i = 0; i < n; i++) { cout << "x[" << i << "] = "; cin >> x[i]; } // 1. Cautare secventiala int cautat; cout << "Ce numar cauti? "; cin >> cautat; bool gasit = false; int pozitie = -1; int contor = 0; for (int i = 0; i < n; i++) { if (x[i] == cautat) { contor++; if (!gasit) { // prima aparitie gasit = true; pozitie = i; } } } cout << endl << "=== REZULTATE ===" << endl; if (gasit) cout << cautat << " gasit la pozitia " << pozitie << ", apare de " << contor << " ori" << endl; else cout << cautat << " NU exista in tablou" << endl; // 2. Cautare cu conditie: primul par int poz_par = -1; for (int i = 0; i < n; i++) { if (x[i] % 2 == 0) { poz_par = i; break; } } if (poz_par != -1) cout << "Primul numar par: " << x[poz_par] << " (pozitia " << poz_par << ")" << endl; else cout << "Nu exista numere pare" << endl; return 0; }
▶ Ruleaza pe OneCompiler

Exercitii practice

Exercitiul 1 (Nivel minim) - Analiza cautarii secventiale

Raspunde la urmatoarele intrebari despre cautarea secventiala:

  1. Avem tabloul int x[8] = {4, 7, 2, 9, 1, 5, 8, 3};. Completeaza un tabel de urmarire (trace table) pentru cautarea secventiala a valorii 5. Coloanele: iteratia, i, x[i], x[i]==5?, actiune.
  2. Pentru acelasi tablou {4, 7, 2, 9, 1, 5, 8, 3}: cate comparatii face cautarea secventiala daca valoarea cautata este 3 (ultimul element)? Dar daca valoarea cautata este 10 (nu exista in tablou)? Scrie numarul de comparatii pentru fiecare caz.
  3. Explica cu cuvintele tale: de ce este necesar break in bucla de cautare secventiala? Ce s-ar intampla fara el?

Raspunde numerotat: 1. ... 2. ... 3. ...

Exercitiul 2 (Nivel standard) - Agenda telefonica

Cerinta: Scrie un program C++ care citeste n numere de telefon (ca numere intregi), apoi permite utilizatorului sa caute un numar. Programul trebuie sa afiseze:

  1. Daca numarul exista in agenda si la ce pozitie
  2. De cate ori apare numarul (un numar poate fi salvat de mai multe ori)
  3. Cate numere din agenda incep cu cifra 7 (conditie: x[i] / 100000 == 7 pentru numere de 6 cifre)

Exemplu input/output: (numere de 6 cifre)

Numere: 721345 734567 721345 756789 734567

Cauta: 734567
Gasit la pozitia 1, apare de 2 ori
Numere care incep cu 7: 5

Indicii:

  • Foloseste cautare secventiala (numerele nu sunt sortate)
  • Combina cautarea cu numararea: parcurge o singura data tabloul si numara aparitiile
  • Un numar de 6 cifre incepe cu 7 daca x[i] / 100000 == 7. Exemplu: 721345 / 100000 = 7. ✓

Exercitiul 3 (Nivel performanta) - Explicatie scrisa

Cerinta: Explica diferenta dintre cautarea secventiala si cautarea binara folosind una dintre urmatoarele analogii:

  1. Optiunea A: Cautarea unui cuvant in dictionar. Cum cauti daca dictionarul nu e ordonat (secventiala) vs. cum cauti intr-un dictionar normal (binara)?
  2. Optiunea B: Cautarea unui prieten intr-un stadion cu 50.000 de oameni. Metoda "strig pe rand" vs. metoda "stiu ca e in sectorul B, randul 15".

In explicatia ta, acopera:

  1. Ce corespunde "tabloului" in analogia ta?
  2. Ce corespunde "elementului cautat"?
  3. De ce metoda binara e mai rapida?
  4. De ce metoda binara nu functioneaza daca "dictionarul nu e ordonat" (tabloul nu e sortat)?

Cuvinte cheie de folosit: cautare secventiala, cautare binara, sortat, comparatie, injumatatire, break, pozitie

Ce ai invatat astazi

  • Ai invatat de ce conteaza cautarea
  • Acum stii cautarea secventiala — verificam pe rand
  • Ai aplicat cautarea secventiala in C++
  • Ai inteles de cate ori apare o valoare (numarare cu contor)
  • Ai gasit primul element care indeplineste o conditie
  • Ai combinat cautarea secventiala + numarare + cautare cu conditie
  • ⭐ APROFUNDARE (optional): Ai explorat cautarea binara — algoritm de liceu/olimpiada, doar in tablouri sortate

Urmatoarea lectie

Continua cu lectia urmatoare pentru a aprofunda cunostintele.

Continua →