Căutări în matrice — găsești o valoare și poziția ei

De ce contează?

Cauți un anumit elev într-un catalog cu rânduri și coloane. Mergi rând cu rând, te uiți la fiecare nume, iar când îl găsești reții exact unde e: rândul și coloana. Asta e căutarea într-o matrice.

Căutare într-o matrice oarecare

Dacă matricea nu are nicio ordine, ca să afli dacă o valoare există trebuie să verifici fiecare element. Parcurgi cu două bucle și compari. Când găsești, reții poziția: perechea (i, j).

Observația-cheie

Pe o matrice nesortată nu există scurtătură: în cel mai rău caz valoarea e ultima, deci trebuie să poți ajunge la toate cele n·m elemente. Costul e O(n·m).

Exemplu pe numere

Căutăm valoarea 7 în matricea 3×4:

L0	2	9	4	1
	0	1	2	3

L1	5	7	3	8
	0	1	2	3

7 e la (1, 1)

L2	6	0	2	9
	0	1	2	3

Parcurgând pe linii, găsim 7 la linia 1, coloana 1 → poziția (1, 1).

Implementare C++

#include <iostream>
using namespace std;

int a[100][100];

int main() {
    int n, m, x;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    cin >> x; // valoarea cautata

    int li = -1, co = -1; // pozitia gasita; -1 = inca negasit
    bool gasit = false;
    for (int i = 0; i < n && !gasit; i++)
        for (int j = 0; j < m; j++)
            if (a[i][j] == x) {
                li = i; co = j;
                gasit = true; // oprim cautarea
                break;        // iesim din bucla pe coloane
            }

    if (gasit) cout << "Gasit la (" << li << ", " << co << ")\n";
    else cout << "Nu exista\n";
    return 0;
}
// pentru x = 7: Gasit la (1, 1)

Condiția !gasit din bucla exterioară plus break-ul din cea interioară opresc căutarea la prima apariție.

Variante des cerute

Toate aparițiile: nu te oprești, ci afișezi fiecare (i, j) cu a[i][j] == x.
Maximul și poziția lui: reții valoarea maximă și (i, j) unde a apărut.
Căutare pe linii sortate: dacă fiecare linie e sortată, poți face căutare binară pe linie → O(n·log m).

Complexitate

Caz	Timp	Spațiu
Matrice nesortată	O(n·m)	O(1)
Linii sortate (binar pe linie)	O(n·log m)	O(1)

Vizualizare

Explorează parcurgerile matricei (comută între linii, coloane, diagonale, spirală):

Greșeli frecvente

Greșeli frecvente de concurs:

Uiți să reții ambii indici. Poziția e (i, j). Dacă reții doar linia, nu mai știi pe ce coloană e elementul.
break iese doar dintr-o buclă. Un singur break părăsește bucla interioară, nu și pe cea exterioară. Folosește un flag (gasit) pentru a opri complet.
Inițializezi poziția cu 0. Dacă pornești li = co = 0, nu distingi „găsit la (0,0)” de „negăsit”. Inițializează cu -1.
Cauți binar pe matrice nesortată. Căutarea binară cere ordine. Pe o matrice oarecare dă rezultate greșite — folosește parcurgerea completă.

Recapitulare

Pe o matrice nesortată, cauți parcurgând tot: O(n·m), și reții poziția ca pereche (i, j).
Pentru prima apariție, oprește căutarea cu un flag + break (un singur break nu ajunge).
Dacă liniile sunt sortate, poți coborî la O(n·log m) cu căutare binară pe fiecare linie.