Informatică Algoritmi
Diferenta intre cautare liniara si binara
Diferența principală între căutarea liniară și cea binară este eficiența: liniara are complexitate O(n), iar binara O(log n). Căutarea liniară funcționează pe orice listă, în timp ce cea binară necesită o listă sortată.
Comparație pe criterii cheie
- Complexitate timp Liniară: O(n) - verifică toate elementele. Binară: O(log n) - înjumătățește intervalul.
- Condiție de aplicare Liniară: orice listă, sortată sau nesortată. Binară: doar liste sortate.
- Utilizare memorie Ambele au complexitate O(1) pentru variabile auxiliare, dar binară poate necesita sortarea prealabilă.
Exemple practice
- Căutare liniară Găsirea unui nume într-o listă de elevi nesortată: verifici fiecare nume până la găsire.
- Căutare binară Căutarea unui cuvânt într-un dicționar: deschizi la mijloc și elimini jumătate la fiecare pas.
- Când să alegi Folosește liniară pentru liste mici sau nesortate; binară pentru liste mari și sortate.
Pentru liste sortate, căutarea binară este întotdeauna mai rapidă; pentru cele nesortate, liniara este singura opțiune.