Modul 01 — Căutarea binară · Clasa a X-a Fable

Ideea: compară cu mijlocul, aruncă o jumătate

Precondiție: vectorul e SORTAT (metodele din clasa a IX-a, Modulul 09!). Compari cu elementul din mijloc: prea mic? arunci jumătatea stângă. Prea mare? pe cea dreaptă.

șir sortat = x =

pași căutare binară: 0

pași căutare liniară (comparație): —

pas	st	dr	mij	a[mij]	decizie

Apasă „Pas" și urmărește cum zona activă se înjumătățește. 👆

Cele două capcane de BAC: ① căutarea binară pe vector NEsortat dă rezultate greșite fără niciun avertisment; ② condiția buclei e st <= dr — cu < strict ratezi cazul când zona activă are un singur element.

Varianta cu poziție — șablonul complet

De cele mai multe ori nu întrebi doar „există?", ci și „PE CE POZIȚIE?". Șablonul de reținut:

1int a[] = {2,5,8,12,16,23,38,56,72,91};

2int n = 10, x = 23, poz = -1;

3int st = 0, dr = n - 1;

4while (st <= dr) {

5 int mij = (st + dr) / 2;

6 if (a[mij] == x) { poz = mij; break; }

7 else if (a[mij] < x) st = mij + 1;

8 else dr = mij - 1;

10cout << (poz != -1 ? poz : -1); // ternar (clasa a IX-a!)

De ce O(log n)? Fiecare pas înjumătățește zona: n → n/2 → n/4 → … → 1. Câte înjumătățiri încap în n? Exact log₂(n). Pentru un milion: 20. Pentru un miliard: 30. Magia dublării, pe dos.

Fișa de sinteză

Metoda, condensată.

Precondiție: vector SORTAT — altfel rezultatul e gunoi, fără eroare vizibilă.

Șablonul: st=0, dr=n−1; cât timp st ≤ dr: mij=(st+dr)/2, compari și tai o jumătate.

a[mij] < x → st = mij+1 · a[mij] > x → dr = mij−1 · egal → GĂSIT.

Complexitate O(log n): 20 de pași pentru un milion de elemente — vs 1.000.000 la liniară.

Nu există? Bucla se termină cu st > dr — zona activă s-a golit.

Preview: la Divide et impera (M11) revii aici — căutarea binară E un caz particular al metodei.

Exersează pe pbinfo.ro:

#508 · medie

Cautare Binara

Determinați dacă x se află într-un șir sortat, cu căutare binară.

Rezolvă pe pbinfo.ro →

#4646 · medie

cb1

Interogări pe un șir sortat: câte numere sunt ≤ x, > x, egale cu x.

Rezolvă pe pbinfo.ro →