Căutarea secvențială și binară. Complexitatea

Pe scurt

1 minesențialul, de recitit oricând

Culorile din lecție:termencifră, datăidee-cheie

• Căutarea secvențială trece prin fiecare element. Căutarea binară înjumătățește la fiecare pas, dar cere tablou ordonat.
• La științele naturii, căutarea binară e temă recurentă, la Subiectul I sau la II.2. La matematică-informatică e în programă, dar în lucrările C/C++ importate nu am găsit niciun item despre ea.
• Complexitatea nu se cere ca formulă separată. Se punctează la III.3, la ambele specializări: 1 p la justificare și 1 p la program.

Urmează · 1 min

Căutarea secvențială

1 min

Vrei să afli dacă x e în tablou. Îl compari cu fiecare element, de la primul la ultimul.

gasit=0;
for(i=0;i<n && gasit==0;i++)
  if(a[i]==x) gasit=1;

Merge pe orice tablou. În cel mai rău caz faci n comparații.

Urmează · 1 min

Căutarea binară

2 min

Dacă tabloul e ordonat, poți face mult mai puțin. Compari cu elementul din mijloc. Dacă x e mai mic, rămâne jumătatea din stânga; dacă e mai mare, cea din dreapta.

st=0; dr=n-1; gasit=0;
while(st<=dr && gasit==0)
{ m=(st+dr)/2;
  if(a[m]==x) gasit=1;
  else
    if(x<a[m]) dr=m-1;
    else st=m+1;
}

Oficial, enunțurile spun „se aplică metoda căutării binare” și cer „succesiunea de elemente ale tabloului a căror valoare se compară cu valoarea lui x”.

La examen, tablourile au de obicei 7 elemente, așa că merită să ții minte forma. Pozițiile sunt numerotate de la 0:

Tabloul poate fi și descrescător. Atunci „jumătatea” se alege invers. Sesiunea specială 2024 folosește (48,24,16,14,9,8,4).

Urmează · 2 min

Patru tipuri de item, pe lucrări oficiale

9 min 2 întrebări la final

Tipul 1: se dă tabloul și x, se cere succesiunea

Model 2023, SN, II.3. Tabloul (3,7,10,12,20,23,65), x=21.

Răspuns: 12, 23, 20 (6 p). Barem: numai 2 p dacă doar prima valoare e bună, numai 4 p dacă primele două sunt bune. Valoarea 21 nu e în tablou, iar succesiunea tot există.

La fel la model 2026, I.2 (7,16,20,25,30,45,70), x=26: 25, 45, 30 (varianta c, 4 p), și la simulare 2025, I.2 (2,3,5,20,25,26,45), x=25: 20, 26, 25 (varianta b, 4 p).

Tipul 2: se dă succesiunea, se cere x

Iunie 2026, varianta 3, SN, II.2. Tabloul (5,7,15,19,21,23,25). Succesiunea e 19, 23, 21. Se cere mulțimea tuturor valorilor întregi ale lui x.

• După 19, s-a mers la dreapta: x>19.
• După 23, s-a mers la stânga: x<23.
• Compararea cu 21 se face pentru orice x care a ajuns aici, oricare ar fi rezultatul ei.

Deci x poate fi 20, 21, 22. Barem: câte 2 p pentru fiecare.

Tot așa: specială 2026, II.2 (10,16,21,26,32,38,50), succesiunea 26, 16, 21 cere două valori; baremul acceptă orice număr din [17,25], câte 3 p. Simulare 2026, I.2 (5,10,14,16,19,21,26), succesiunea 16, 21, 19: mulțimea {17,18,19,20} (varianta d, 4 p).

Tipul 3: se dă succesiunea, se cere tabloul

Model 2027, SN, I.2. Un tablou cu 7 elemente, x=27, succesiunea 49, 10, 27. Răspunsul e D, (5,10,27,49,50,51,64), 4 p.

Din succesiune: 49 e pe poziția 3, 10 pe poziția 1, 27 pe poziția 2, iar tabloul trebuie să fie ordonat. Varianta C, (10,11,27,49,50,59,64), are 11 pe poziția 1, deci cade. Variantele A și B nu sunt ordonate.

La fel: iulie 2024, I.2, succesiunea 14, 24, 16, răspuns (4,8,9,14,16,24,48), varianta c. August 2026, I.3, succesiunea 49, 21, 23, răspuns (-10,21,23,49,50,70,95), varianta c.

Tipul 4: numărul de comparații

La 11 elemente, prima comparație e la poziția 5, a doua la 2 sau 8.

Urmează · 9 min

Complexitatea: două criterii

5 min o întrebare la final

Programa spune la 6.8: criteriile de eficiență sunt durata de executare și spațiul de memorie utilizat. Pe scurt, cât durează și câtă memorie ocupă.

Nu am găsit niciun item care să ceară ordinul de complexitate ca răspuns. Complexitatea apare la III.3, unde enunțul spune „proiectați un algoritm eficient”. Baremele cer un algoritm liniar. Cuvântul „liniar” apare în toate cele 67 de bareme C/C++ importate, iar 11 scriu explicit „liniar (de complexitate O(n))”, de exemplu august 2024, specială 2024 și rezerva 2026.

Numele de logaritmic și pătratic nu vin din bareme. Le găsești aici ca să ai cuvinte pentru diferență. Formularea sigură pentru examen rămâne „liniar”, pe care o și folosește baremul.

Urmează · 5 min

Oficial: simulare 2026, MI, III.3

7 min

În bac.txt sunt x și y, apoi un șir de cel mult 10⁶ numere ordonate crescător. Se afișează câte valori pare distincte din șir sunt în [x,y]. Pentru 6 11 și șirul 1 1 1 2 2 3 5 5 5 5 6 6 7 8 10 10 12 15 15 21 21, se afișează 3, adică 6, 8, 10.

Ideea: fiind ordonate, valorile egale sunt una lângă alta. Deci ajunge să compari valoarea curentă cu cea de dinainte. Nu ții șirul în memorie și nu cauți nimic.

#include <iostream>
#include <fstream>
using namespace std;

int main()
{ ifstream f("bac.txt");
  int x,y,crt,ant=0,nr=0;
  f>>x>>y;
  while(f>>crt)
  { if(crt!=ant && crt%2==0)
      if(crt>=x && crt<=y)
        nr++;
    ant=crt;
  }
  f.close();
  cout<<nr;
  return 0;
}

Baremul indică aceeași soluție, cu ant inițializat cu 0 și cu crt, și adaugă că parcurgerea se poate opri la crt>y.

La științele naturii, aceeași simulare cere valorile pare distincte mai mari sau egale cu x. Pentru 5 și același șir, răspunsul e 4: 6, 8, 10, 12.

Urmează · 7 min

Ce se cere la BAC

2 mincum apare la examen

Urmează · 2 min

Greșeli care costă puncte

2 mincapcanele de evitat

• Mijlocul rotunjit în sus: m=(st+dr)/2 e împărțire întreagă. La 0 și 3 mijlocul e 1.
• Tabloul neordonat ales ca răspuns la grilă.
• Uiți că x poate lipsi din tablou când se cere mulțimea tuturor valorilor.
• Ai dat și indicii, în loc de valori, când se cere succesiunea de elemente.
• st=m în loc de st=m+1: bucla poate să nu se termine.
• Justificare goală la a): spune de ce e liniar și de ce ai folosit puțină memorie, dacă enunțul cere amândouă criteriile.
• Tablou imens la III.3, când o variabilă era de ajuns.

Urmează · 2 min