SISergiu Ilincameditații informatică
Meniu

clasa a X-a · Tablouri unidimensionale · lecția 5

Căutarea secvențială, căutarea binară și interclasarea

60 mintoate profilurile

Înainte de lecția asta: X.4 Sortarea vectorilor: bule, selecție, inserție (și sort din STL)

Ce vei ști după lecție

  • Cauți o valoare într-un vector oarecare (secvențial) și într-un vector sortat (binar).
  • Înțelegi de ce căutarea binară face doar ~log₂ n pași.
  • Găsești prima poziție cu a[i] ≥ x (varianta de căutare binară cea mai utilă).
  • Interclasezi doi vectori sortați într-un al treilea, în timp liniar.
  • Calculezi reuniunea și intersecția a două mulțimi sortate.

Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓

Clasa a X-aLecția 5 din 13 · mai sunt 8Urmează: X.6 · Vectori caracteristici, vectori de frecvență și Ciurul lui EratosteneVezi toate lecțiile
Cuprins

Fișiere PDF și de lucru

1. Căutarea secvențială

Parcurgem vectorul până găsim valoarea:

int poz = -1;
for (int i = 1; i <= n && poz == -1; i++)
    if (a[i] == x) poz = i;

În cel mai rău caz verificăm toate cele n elemente: O(n).

2. Căutarea binară (doar pe vector sortat!)

Ca la ghicitul unui număr între 1 și 100: „e mai mare sau mai mic?”. La fiecare întrebare înjumătățim intervalul. Cauți un cuvânt în dicționar: deschizi la mijloc, vezi dacă ești înainte sau după, și continui pe jumătatea potrivită.

Căutarea binară

#include <iostream>
using namespace std;

int a[100001], n, x;

int main()
{
    cin >> n >> x;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int st = 1, dr = n, poz = -1;
    while (st <= dr && poz == -1)
    {
        int mij = (st + dr) / 2;
        if (a[mij] == x) poz = mij;
        else if (a[mij] < x) st = mij + 1;   // x e în dreapta
        else dr = mij - 1;                   // x e în stânga
    }
    cout << poz;
    return 0;
}

Pentru n = 1 000 000 face cel mult 20 de pași (2²⁰ ≈ 10⁶). Complexitate: O(log n).

Atenție — greșeli frecvente

Căutarea binară funcționează doar pe vectori sortați. Pe un vector nesortat dă rezultate greșite fără niciun avertisment.

De ce așa?

De ce st = mij + 1 și dr = mij - 1, nu st = mij? Elementul mij a fost deja verificat și nu e x; îl excludem. Cu st = mij intervalul ar putea să nu se micșoreze (când st + 1 == dr, mij == st), iar bucla ar fi infinită.

Urmărire

a = (2, 5, 8, 12, 16, 23, 38, 56, 72, 91), căutăm x = 23:

st dr mij a[mij] decizie
1 10 5 16 16 < 23 → st = 6
6 10 8 56 56 > 23 → dr = 7
6 7 6 23 găsit la poziția 6

Pentru x = 40 (nu există):

st dr mij a[mij] decizie
1 10 5 16 st = 6
6 10 8 56 dr = 7
6 7 6 23 st = 7
7 7 7 38 st = 8
8 7 — st > dr → nu există

La BAC

La grile se întreabă des: „Ce valori ia mij?” sau „Câte comparații se fac până se găsește/nu se găsește x?”. Fă tabelul ca mai sus.

Varianta „prima poziție cu a[i] ≥ x”

Mai utilă decât căutarea exactă: răspunde la „câte elemente sunt mai mici decât x?”, „unde aș insera x?”.

#include <iostream>
using namespace std;

int a[100001], n, x;

int main()
{
    cin >> n >> x;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int st = 1, dr = n, rez = n + 1;     // n + 1 = „nu există”
    while (st <= dr)
    {
        int mij = (st + dr) / 2;
        if (a[mij] >= x) { rez = mij; dr = mij - 1; }   // e candidat, căutăm mai la stânga
        else st = mij + 1;
    }
    cout << rez;       // elementele mai mici decât x sunt exact a[1..rez-1]
    return 0;
}

Câte elemente sunt în intervalul [x, y]? → (prima poziție cu a[i] > y) − (prima poziție cu a[i] ≥ x).

De ce așa?

De ce nu ne oprim când găsim x? Pot exista mai multe copii (de exemplu 5 5); noi vrem prima. Reținem rez = mij și continuăm în stânga, căutând o apariție și mai de la început. Ideea „păstrez un candidat bun și caut unul mai bun” se numește căutare binară pe răspuns.

3. Interclasarea

Avem doi vectori sortați a (n elemente) și b (m elemente). Vrem un vector c sortat cu toate elementele. Ideea: comparăm „capetele” și îl luăm pe cel mai mic, ca la două cozi care se îmbină într-una singură.

Interclasare

#include <iostream>
using namespace std;

int a[1001], b[1001], c[2002], n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int j = 1; j <= m; j++) cin >> b[j];
    int i = 1, j = 1, k = 0;
    while (i <= n && j <= m)
        if (a[i] < b[j]) c[++k] = a[i++];
        else c[++k] = b[j++];
    while (i <= n) c[++k] = a[i++];      // ce a rămas din a
    while (j <= m) c[++k] = b[j++];      // ce a rămas din b
    for (int t = 1; t <= k; t++)
        cout << c[t] << ' ';
    return 0;
}
a[i] b[j] se ia c
1 2 1 (din a) 1
4 2 2 (din b) 1 2
4 3 3 (din b) 1 2 3
4 9 4 (din a) 1 2 3 4
9 9 9 (din b, egal) 1 2 3 4 9
9 15 9 (din a) 1 2 3 4 9 9
10 15 10 (din a), a se termină 1 2 3 4 9 9 10
— 15, 20 copiez restul din b 1 2 3 4 9 9 10 15 20

Complexitate: O(n + m): mult mai bine decât „le pun pe toate și sortez” (O((n+m)²) cu bule).

Sfat

c[++k] = a[i++]; face trei lucruri: crește k, copiază a[i] în c[k], apoi crește i. E o scriere compactă și foarte des folosită: asigură-te că o înțelegi.

De ce așa?

De ce cele două bucle de la final? Când unul dintre vectori se termină, celălalt mai poate avea elemente, toate mai mari decât tot ce am scris. Doar unul din cele două while se execută efectiv; celălalt are condiția falsă din start.

Reuniune și intersecție (mulțimi sortate, fără duplicate)

// intersecția: doar elementele comune
int i = 1, j = 1, k = 0;
while (i <= n && j <= m)
    if (a[i] == b[j]) { c[++k] = a[i]; i++; j++; }
    else if (a[i] < b[j]) i++;
    else j++;

Pentru reuniune, la egalitate pui elementul o singură dată și avansezi în ambii vectori.

4. Interclasare fără memorie (Bac III.3)

Dacă cele două șiruri sortate sunt în fișiere și sunt foarte mari, poți interclasa citind câte un element din fiecare și scriind direct rezultatul, fără vectori. Același algoritm, dar a[i] devine „valoarea citită curent din primul fișier”.

5. Greșeli frecvente

Greșeala Efect Corect
căutare binară pe vector nesortat rezultate greșite sortează întâi
while (st < dr) în loc de st <= dr pierzi cazul cu un element st <= dr
st = mij buclă infinită st = mij + 1
uiți cele două bucle de la interclasare pierzi elementele rămase copiază restul
(st + dr) / 2 cu valori foarte mari depășire de int st + (dr - st) / 2

6. La BAC

La BAC

Grilele de căutare binară cer valorile lui mij sau numărul de pași (tabelul din lecție). Cele de interclasare cer vectorul rezultat sau al câtelea element e un anumit număr. La II.3 poți fi pus să scrii interclasarea; la III.3, interclasarea din fișiere fără vectori.

7. Exersează pe hârtie

Răspunsurile sunt la final: încearcă întâi singur.

1. Câți pași (valori ale lui mij) face căutarea binară ca să constate că 40 nu apare în vectorul din secțiunea 2?

2. Interclasează (pe hârtie) (1, 4, 9, 10) cu (2, 3, 9, 15, 20).

3. Se dau doi vectori sortați. Afișează elementele din a care nu apar în b (diferența), în O(n + m).

4. Care este numărul maxim de pași ai căutării binare pentru n = 1000? Dar pentru n = 10⁶?

5. Ce rezultat obții dacă aplici căutarea binară pentru x = 5 pe vectorul nesortat (5, 1, 3, 9)?

6. În vectorul sortat (1, 3, 5, 5, 7, 9), câte elemente sunt în intervalul [3, 7]? Folosește „prima poziție ≥ x” de două ori.

7. De ce se scrie st + (dr - st) / 2 în loc de (st + dr) / 2 pentru indici mari?

8. Mai departe (pentru cine vrea mai mult)

lower_bound și upper_bound. În C++ standard, lower_bound(a+1, a+n+1, x) - a dă exact „prima poziție cu a[i] ≥ x”, iar upper_bound pe „prima poziție cu a[i] > x”. Acum știi ce fac înăuntru.

Căutare binară pe răspuns. Nu doar în vectori: dacă răspunsul unei probleme are proprietatea „dacă x merge, atunci și x+1 merge”, îl cauți binar printre numere. Exemplu: „care e cea mai mică viteză cu care ajungi la timp?”. Este o tehnică des folosită la concursuri.

Căutare binară la depanare. git bisect caută binar versiunea de cod care a introdus un bug: dintre 1000 de versiuni, 10 teste. Aceeași idee, aplicată la istoricul unui proiect.

Merge sort. Interclasarea este cheia sortării prin interclasare: împarți vectorul în două, sortezi fiecare jumătate și le interclasezi. Timp O(n log n), garantat; o implementezi la recursivitate (clasa a XI-a).

Rezumat

  • Secvențial: O(n), merge pe orice vector.
  • Binar: O(log n), doar pe vector sortat; st, dr, mij.
  • Prima poziție ≥ x: reții rez = mij și cauți mai la stânga.
  • Interclasare: compari capetele, iei minimul, copiezi restul. O(n + m).

Fișa de lucru

Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.

Fișă de lucru · 6 pagini · 90 min

Căutare binară și interclasare

  • Urmărești valorile lui st, dr și mij și numeri pașii căutării binare, ca la grilele de BAC.
  • Folosești „prima poziție ≥ x” și „ultima poziție ≤ x” pentru numărări și cel mai apropiat element.
  • Interclasezi, intersectezi și reunești vectori sortați în O(n + m), inclusiv din fișier.

Te-ai blocat la un exercițiu?

Probleme de lucru

Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.

  • cautare-binara#508

    Pentru fiecare y[j], există în x?

    medie
  • cb-0#4856

    ușoară
  • interclasare#241

    ușoară

Temă

Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.

  • cb#2276

    Câte elemente sunt într-un interval: două căutări binare.

    ușoară
  • interclasare1#250

    medie
  • interclasare2#251

    medie
  • multimi1#530

    Reuniune și intersecție.

    medie
  • interclasare3#284

    medie
  • cautare#507

    ușoară

Pentru cei care vor mai mult

  • irdds#3974

    medie
  • comun#2668

    medie

Grile din subiectele de BAC

Exerciții de tip grilă din variantele de Bacalaureat. Se rezolvă pe pbinfo.ro, care îți verifică imediat răspunsul.

Citește și exersează în plus

Te-ai blocat la lecția asta?

Scrie-mi ce nu iese și vedem împreună de unde se blochează.

Răspunsuri

Exersează pe hârtie

1. 4 pași: mij = 5, 8, 6, 7 (valorile 16, 56, 23, 38), apoi st > dr.

2. (1, 2, 3, 4, 9, 9, 10, 15, 20).

3.

#include <iostream>
using namespace std;

int a[1001], b[1001], n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int j = 1; j <= m; j++) cin >> b[j];
    int i = 1, j = 1;
    while (i <= n)
    {
        while (j <= m && b[j] < a[i]) j++;     // sar peste elementele mai mici din b
        if (j > m || b[j] != a[i])
            cout << a[i] << ' ';               // a[i] nu apare în b
        i++;
    }
    return 0;
}

Fiecare indice doar crește: O(n + m).

4. Pentru n = 1000: 10 pași (2¹⁰ = 1024 ≥ 1001). Pentru n = 10⁶: 20 de pași (2²⁰ ≈ 1,05·10⁶).

5. Se obține „nu există”, deși 5 este în vector. Pași: mij = 2, a[2] = 1 < 5 → st = 3; mij = 3, a[3] = 3 < 5 → st = 4; mij = 4, a[4] = 9 > 5 → dr = 3, apoi st > dr. Căutarea binară presupune vector sortat; pe unul nesortat poate rata elemente.

6. 4: prima poziție ≥ 3 este 2, prima poziție > 7 este 6 (elementul 9), deci 6 − 2 = 4 (3, 5, 5, 7).

7. st + dr poate depăși valoarea maximă a lui int când st și dr sunt mari (de exemplu 1,5·10⁹ + 1,5·10⁹), iar rezultatul devine negativ. st + (dr - st) / 2 nu depășește niciodată dr. Bug celebru, rămas ani în biblioteca standard Java.