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

> Pagina: https://bacalaurescu.ro/informatica/lectii/algoritmi-clasici-bac/cautare-binara
> Markdown: https://bacalaurescu.ro/informatica/lectii/algoritmi-clasici-bac/cautare-binara.md
> Sursa: Bacalaurescu (bacalaurescu.ro), conținut gratuit pentru BAC 2027.

Materia: [Informatică](https://bacalaurescu.ro/informatica)

Capitolul: [Algoritmi clasici de BAC](https://bacalaurescu.ro/informatica/lectii/algoritmi-clasici-bac)
Actualizat: 2026-09-22

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

## 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.

1. `st = 0`, `dr = n - 1`;
2. 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`;
3. 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 |

> [!RETINE]
> 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

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