Informatică Algoritmi
Ce este un algoritm de cautare liniara?
Un algoritm de căutare liniară este o metodă care verifică fiecare element al unei liste secvențial până găsește valoarea dorită. Este simplu dar ineficient pentru liste mari.
Pașii căutării liniare
- 1 Pasul 1 - Parcurge lista Începe de la primul element și mergi la următorul.
- 2 Pasul 2 - Compară La fiecare element, verifică dacă este egal cu valoarea căutată.
- 3 Pasul 3 - Găsește sau termină Dacă se găsește, returnează poziția; dacă se ajunge la sfârșit, returnează 'nu există'.
Exemplu numeric
- 1 Lista și valoarea Lista: [7, 3, 9, 2]; Valoarea căutată: 9
- 2 Pasul 1 Verifică 7 - nu este 9.
- 3 Pasul 2 Verifică 3 - nu este 9.
- 4 Pasul 3 Verifică 9 - este egal, returnează index 2.
Complexitate
- Cazul mediu O(n), unde n este numărul de elemente - trebuie verificată în medie jumătate din listă.
- Cazul cel mai defavorabil O(n) - dacă valoarea este la sfârșit sau nu există, se parcurge întreaga listă.
- Cazul cel mai favorabil O(1) - dacă valoarea este primul element.
Folosește căutarea liniară pentru liste mici sau nesortate; pentru liste mari și sortate, căutarea binară este mai rapidă.