# Prelucrări clasice de vectori: maxim, sortare, căutare

> Pagina: https://bacalaurescu.ro/informatica/lectii/tablouri-unidimensionale/prelucrari-clasice-vectori
> Markdown: https://bacalaurescu.ro/informatica/lectii/tablouri-unidimensionale/prelucrari-clasice-vectori.md
> Sursa: Bacalaurescu (bacalaurescu.ro), conținut gratuit pentru BAC 2027.

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

Capitolul: [Tablouri unidimensionale](https://bacalaurescu.ro/informatica/lectii/tablouri-unidimensionale)
Actualizat: 2026-11-01

Cele trei prelucrări care apar constant la BAC, cu implementări complete.

## Pe scurt pentru BAC

- Când cauți și poziția maximului, actualizezi `poz = i` împreună cu `maxim` la fiecare valoare mai mare.
- La bubble sort, după fiecare trecere cel mai mare element ajunge la finalul zonei nesortate, iar pentru descrescător inversezi comparația.
- Căutarea liniară merge pe orice vector și are complexitatea O(n), iar căutarea binară înjumătățește intervalul la fiecare pas, O(log n).
- Vectorul de frecvență `fr[x]` reține de câte ori apare x și se poate folosi când valorile sunt mici.

## Maximul și poziția lui

```cpp
int maxim = v[0], poz = 0;
for (int i = 1; i < n; i++)
    if (v[i] > maxim) {
        maxim = v[i];
        poz = i;
    }
```

Inițializezi cu PRIMUL element, nu cu 0 (vectorul poate avea doar valori negative).

## Sortarea prin interschimbare (bubble sort)

```cpp
for (int i = 0; i < n - 1; i++)
    for (int j = 0; j < n - i - 1; j++)
        if (v[j] > v[j + 1]) {
            int aux = v[j];
            v[j] = v[j + 1];
            v[j + 1] = aux;
        }
```

După fiecare trecere, cel mai mare element "se scufundă" la finalul zonei nesortate. Pentru descrescător, inversezi comparația (`<`).

**Urmărire pe [3, 1, 2]**: trecerea 1: (3,1)→schimb → [1,3,2]; (3,2)→schimb → [1,2,3]. Trecerea 2: (1,2) ok. Sortat. ✓

## Căutarea

**Liniară** (vector oarecare): parcurgi și compari, O(n).

```cpp
int gasit = 0;
for (int i = 0; i < n; i++)
    if (v[i] == x) { gasit = 1; break; }
```

**Binară** (DOAR pe vector SORTAT): înjumătățești intervalul la fiecare pas, O(log n).

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

Pentru x = 7 în [1, 3, 5, 7, 9]: m=2 (5<7) → st=3; m=3 (7=7) → găsit în 2 pași. ✓

## Frecvența elementelor

```cpp
int fr[101] = {0};
for (int i = 0; i < n; i++)
    fr[v[i]]++;
```

Vectorul de frecvență: fr[x] = de câte ori apare x. Merge când valorile sunt mici (aici 0-100).

> [!RETINE]
> Căutarea binară cere vector SORTAT: pe vector nesortat dă rezultate greșite fără niciun mesaj de eroare. La BAC verifică întâi ipoteza de sortare.

## Greșeli frecvente

1. Maxim inițializat cu 0 în loc de v[0]: pică pe vectori cu numere negative.
2. La bubble sort, limita interioară e n-i-1: fără -1 ieși din vector la v[j+1].
3. La binară, actualizează st = m+1 / dr = m-1, nu st = m (buclă infinită).