Informatică Algoritmi
Algoritmi de cautare in vectori
Algoritmii de căutare în vectori sunt metode pentru a găsi un element specific într-o listă ordonată sau neordonată de date. Acești algoritmi compară elementele vectorului cu valoarea căutată și returnează poziția sau indică absența. Sunt esențiali în programare pentru eficiența căutării.
Algoritmi pentru vectori neordonați
- Căutare liniară Verifică fiecare element din vector în ordine până găsește valoarea. Complexitate: O(n), unde n este numărul de elemente. Exemplu: căutarea numărului 7 în [3, 1, 7, 4].
- Căutare cu hashing Folosește o funcție hash pentru a mapa valorile la poziții, permițând căutarea rapidă. Complexitate medie: O(1), dar necesită structuri de date suplimentare.
Algoritmi pentru vectori ordonați
- Căutare binară Împarte vectorul în jumătăți repetat, comparând valoarea căutată cu elementul din mijloc. Complexitate: O(log n). Exemplu: căutarea lui 10 în [2, 5, 8, 10, 12].
- Căutare interpolată Îmbunătățește căutarea binară estimând poziția valorii bazându-se pe distribuție. Eficientă pentru date uniform distribuite.
Folosește căutarea binară pentru vectori mari și ordonați pentru a reduce timpul de execuție.