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 aplici cautarea binara - doar in tablouri sortate
  • Sa aplici de cate ori apare o valoare

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!

Cautarea binara - DOAR in tablouri sortate!

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 algoritmilor de cautare

Raspunde la urmatoarele intrebari despre cautare:

  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. Avem tabloul sortat int x[8] = {1, 2, 3, 4, 5, 7, 8, 9};. Completeaza un tabel de urmarire pentru cautarea binara a valorii 7. Coloanele: pas, st, dr, mij, x[mij], comparatie, actiune.
  3. Explica de ce cautarea secventiala functioneaza pe orice tablou, dar cautarea binara doar pe tablouri sortate. Da un exemplu concret in care cautarea binara esueaza pe un tablou nesortat.

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] / 1000000 == 7 pentru numere de 7 cifre)

Exemplu input/output:

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
  • Pentru numere care incep cu 7: x[i] / 100000 == 7 (daca numerele au 6 cifre)

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 descoperit cautare secventiala in c++
  • Ai explorat cautarea binara - doar in tablouri sortate
  • Ai inteles de cate ori apare o valoare
  • Ai invatat gaseste primul element care indeplineste o conditie
  • Acum stii cautare secventiala + numarare + cautare cu conditie

Urmatoarea lectie

Continua cu lectia urmatoare pentru a aprofunda cunostintele.

Continua →