Parcurgerea vectorilor

De ce contează?

Ai un raft cu cărți numerotate de la 0. Ca să afli câte pagini ai în total sau care e cartea cea mai groasă, treci pe rând prin fiecare, de la prima la ultima. A „parcurge" un vector înseamnă exact asta: vizitezi fiecare element, o singură dată, în ordine.

Ce este un vector și cum îl parcurgi

Un vector ține mai multe valori de același tip, accesibile prin index. Indicii pornesc de la 0: un vector cu n elemente are pozițiile 0 ... n−1.

Parcurgerea standard cu for:

for (int i = 0; i < n; i++) {
    // foloseste v[i]
}

v	5	3	8	1	9	2
i	0	1	2	3	4	5
			i

La pasul i = 2, parcurgerea vizitează v[2] = 8. Indicele crește pas cu pas, de la 0 la n−1.

Observația-cheie

Condiția corectă e i < n, nu i <= n. Cu i <= n ai accesa v[n], o poziție care nu există — citești gunoi sau provoci crash. E cea mai frecventă eroare la vectori.

Trei prelucrări clasice într-o singură trecere

Suma, maximul și numărarea elementelor pare — toate se fac dintr-o singură parcurgere:

#include <iostream>
using namespace std;

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

    long long suma = 0;          // long long: suma poate fi mare
    int maxim = v[0];            // initializam cu primul element
    int nrPare = 0;
    for (int i = 0; i < n; i++) {
        suma += v[i];
        if (v[i] > maxim) maxim = v[i];
        if (v[i] % 2 == 0) nrPare++;
    }
    cout << suma << " " << maxim << " " << nrPare << "\n";
    return 0;
}

Pentru v = {5, 3, 8, 1, 9, 2}: suma 28, maxim 9, 2 elemente pare (8 și 2).

Observația-cheie

Maximul se inițializează cu v[0], nu cu 0. Dacă vectorul ar avea toate valorile negative, pornirea de la 0 ar da un maxim greșit. Pornește mereu de la primul element real.

Parcurgere cu condiție: prima poziție a unei valori

Uneori te oprești devreme, când ai găsit ce căutai:

int pozitie = -1;               // -1 = negasit
for (int i = 0; i < n; i++) {
    if (v[i] == cautat) {
        pozitie = i;
        break;                  // ne oprim la prima aparitie
    }
}

Complexitate

Prelucrare	Timp	Spațiu
sumă / maxim / numărare	O(n)	O(1)
căutare cu oprire	O(n) în cel mai rău caz	O(1)

O singură trecere = O(n). Poți calcula mai multe lucruri în aceeași buclă, fără cost suplimentar.

Vizualizare

Urmărește cum indicele avansează prin vector și cum se actualizează suma și maximul la fiecare pas:

Indiciu

Folosește ← → ca să pășești manual prin vector. Observă că maximul se schimbă doar când elementul curent îl depășește — în rest rămâne neatins.

Greșeli frecvente

Capcane reale la parcurgerea vectorilor:

Off-by-one: i <= n accesează v[n], în afara vectorului → gunoi sau crash. Folosește i < n.
Maxim inițializat cu 0: pe valori negative dă rezultat greșit. Pornește de la v[0].
Overflow la sumă: acumulator int se sparge la vectori mari. Folosește long long.
Citire incompletă: uiți să citești toate cele n elemente și lucrezi cu poziții necitite (gunoi).

De reținut

Indicii merg 0 ... n−1 → condiția i < n; v[n] nu există.
Inițializează maximul cu v[0], nu cu 0; folosește long long pentru sumă.
Mai multe prelucrări încap într-o singură trecere O(n).