Căutare liniară

De ce contează?

Cauți un elev pe lista clasei și nu știi în ce ordine sunt scrisi: citești fiecare nume de sus în jos până îl găsești sau ajungi la final. Asta e căutarea liniară — simplă, directă, fără trucuri.

Ce este căutarea liniară?

Căutarea liniară parcurge vectorul de la stânga la dreapta și verifică fiecare element până îl găsește pe cel dorit (sau epuizează lista).

Nu cere vector sortat. E cea mai simplă strategie de căutare și primul lucru la care apelezi când nu ai nicio informație despre ordinea datelor.

Algoritmul

gasit ← fals, pozitie ← -1
pentru i de la 0 la n-1:
    daca v[i] = valoare_cautata:
        gasit ← adevarat
        pozitie ← i
        stop   ← prima aparitie

Implementare C++

#include <iostream>
using namespace std;

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

    int x;
    cin >> x;           // valoarea de cautat

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

    if (pozitie != -1)
        cout << "Gasit la pozitia " << pozitie << "\n";
    else
        cout << "Nu exista\n";
    return 0;
}

Toate aparițiile

Dacă vrei toate pozițiile în care apare valoarea, renunți la break și parcurgi vectorul complet:

bool gasit = false;
for (int i = 0; i < n; i++) {
    if (v[i] == x) {
        cout << i << " ";
        gasit = true;
    }
}
if (!gasit) cout << "Nu exista\n";

Complexitate

Caz	Timp
Cel mai bun (prima poziție)	O(1)
Mediu	O(n/2) = O(n)
Cel mai rău (absent)	O(n)

Observația-cheie

Dacă vectorul e sortat, poți folosi căutarea binară — O(log n). Pentru n = 1.000.000: liniară face 1.000.000 pași, binară face ~20. La concursuri, preferă căutarea binară când vectorul e deja sortat.

Vizualizare

Urmărește cum cursorul verifică fiecare element pe rând, de la stânga la dreapta, până găsește valoarea căutată:

Greșeli frecvente

Greșeala 1: Returnezi pozitie = 0 ca „negăsit" — dar 0 e o poziție validă! Folosește -1 pentru „negăsit".

Greșeala 2: Vrei toate aparițiile dar ai break în buclă — te oprești la prima apariție și ratezi restul.

Greșeala 3: if (v[i] = x) în loc de if (v[i] == x) — = e atribuire, nu comparație. Compilatorul poate da un avertisment, dar codul compilează și produce rezultate greșite.

Recapitulare

Căutarea liniară parcurge vectorul element cu element până găsește valoarea.
Complexitate O(n); nu necesită vector sortat.
Returnează -1 (sau afișează mesaj) dacă valoarea lipsește.