Capitolul 18 · Lecția 18.4 din 4

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

Cele două metode, condiția obligatorie a căutării binare și capcana depășirii la mijloc.

Capitolul 18: Algoritmi clasici de BAC

Pe această pagină5 secțiuni

Căutarea secvențială

Parcurgi vectorul de la început până găsești elementul sau ajungi la capăt.

Complexitate: $O(n)$ .
Avantaj: funcționează pe orice vector, sortat sau nu.

Căutarea binară

Condiție obligatorie: vectorul trebuie să fie SORTAT. Pe un vector nesortat dă rezultate greșite, nu eroare, ceea ce e mai periculos.

Ideea: compari cu elementul din mijloc și elimini jumătate din intervalul de căutare la fiecare pas.

st = 0, dr = n - 1;
cât timp st <= dr:
- mij = (st + dr) / 2;
- dacă v[mij] == x, ai găsit;
- dacă v[mij] < x, cauți în dreapta: st = mij + 1;
- altfel cauți în stânga: dr = mij - 1;
dacă bucla se termină, elementul nu există.

Complexitate: $O(\log n)$ . Pentru un milion de elemente, cel mult 20 de pași.

Capcana depășirii

mij = (st + dr) / 2 poate depăși tipul întreg când st și dr sunt mari, pentru că suma lor depășește limita înainte de împărțire.

Varianta sigură: $mij = st + \frac{dr - st}{2}$

Matematic e același lucru, dar nu trece niciodată prin suma mare. E un bug celebru, care a stat ascuns ani de zile în biblioteci standard.

Comparație

	Secvențială	Binară
Vector sortat	nu e nevoie	obligatoriu
Complexitate	$O(n)$	$O(\log n)$
1.000.000 elemente	până la 1.000.000 pași	cel mult 20

Reține

Dacă subiectul spune „vector ordonat crescător", e un semnal clar că se așteaptă căutare binară. Dacă nu spune, folosește secvențială sau sortează întâi.

Greșeli frecvente

Se aplică binară pe vector nesortat. Rezultatul e greșit, dar programul nu dă eroare.
Se scrie st = mij în loc de st = mij + 1, și bucla nu se mai termină.
Se folosește st < dr în loc de st <= dr, și se ratează elementul când intervalul are un singur element.

Exemplul, în 4 limbaje

Alege limbajul în care dai examenul. Poți edita codul și îl poți rula direct aici. Programa oficiala de BAC (proba E.d) cere Pascal sau C/C++, la alegere. Python apare in manualele noi si e pus aici pentru inteles, nu ca limbaj de examen.

#include <iostream>
using namespace std;

int main() {
    int n, x, v[100];
    cin >> n >> x;
    for (int i = 0; i < n; i++) cin >> v[i];

    int st = 0, dr = n - 1, gasit = -1, pasi = 0;
    while (st <= dr) {
        pasi++;
        int mij = st + (dr - st) / 2;
        if (v[mij] == x) { gasit = mij; break; }
        if (v[mij] < x) st = mij + 1;
        else dr = mij - 1;
    }

    if (gasit >= 0) cout << "gasit pe pozitia " << gasit << " in " << pasi << " pasi";
    else cout << "negasit in " << pasi << " pasi";
    return 0;
}

Date de intrarese trimit programului la citire

Instrumente pentru lecția asta

Căutarea binară, pas cu pas

Alege valoarea căutată și urmărește cum zona de căutare se înjumătățește la fiecare comparație, cu explicații la fiecare pas.

Se încarcă instrumentul…

Explorează interactiv