nici măcar o singură trecere de o zi, când nu trebuie să căutăm ceva în viața noastră de zi cu zi, chei auto, Cărți, stilou, încărcător mobil și ce nu. La fel este viața unui computer, există atât de multe date stocate în el, încât ori de câte ori un utilizator cere unele date, computerul trebuie să-și caute memoria pentru a căuta datele și a le pune la dispoziția utilizatorului. Și computerul are propriile tehnici pentru a căuta rapid prin memoria sa, despre care puteți afla mai multe în seria noastră de tutoriale pentru sistemul de Operare.
ce se întâmplă dacă trebuie să scrieți un program pentru a căuta un anumit număr într-o matrice? Cum o vei face?
Ei bine, pentru a căuta un element într-o matrice dată, există doi algoritmi populare disponibile:
- căutare liniară
- Căutare binară
căutare liniară
căutare liniară este un algoritm de căutare foarte simplu și simplu. În căutarea liniară, căutăm un element sau o valoare într-o matrice dată traversând matricea de la început, până când se găsește elementul sau valoarea dorită.
compară elementul de căutat cu toate elementele prezente în matrice și atunci când elementul este potrivit cu succes, returnează indexul elementului din matrice, altfel returnează -1.
căutarea liniară este aplicată pe liste nesortate sau neordonate, atunci când există mai puține elemente într-o listă.
caracteristici ale algoritmului de căutare liniară
- este utilizat pentru lista mică de elemente nesortate și neordonate.
- are o complexitate temporală de O(n), ceea ce înseamnă că timpul depinde liniar de numărul de elemente, ceea ce nu este rău, dar nici atât de bun.
- are o implementare foarte simplă.
vom implementa algoritmul de căutare liniară în următorul tutorial.
Căutare binară
Căutare binară este utilizat cu matrice sortate sau listă. În căutarea binară, urmăm următorii pași:
- începem prin a compara elementul care trebuie căutat cu elementul din mijlocul listei/matricei.
- dacă obținem un meci, returnăm indicele elementului din mijloc.
- dacă nu obținem o potrivire, verificăm dacă elementul care trebuie căutat este mai mic sau mai mare decât valoarea elementului din mijloc.
- Dacă elementul/numărul care trebuie căutat are o valoare mai mare decât numărul din mijloc, atunci alegem elementele din partea dreaptă a elementului din mijloc(deoarece lista/matricea este sortată, deci în dreapta, vom avea toate numerele mai mari decât numărul din mijloc) și începem din nou de la Pasul 1.
- Dacă elementul/numărul de căutat are o valoare mai mică decât numărul din mijloc, atunci alegem elementele din partea stângă a elementului din mijloc și începem din nou de la Pasul 1.
căutarea binară este utilă atunci când există un număr mare de elemente într-o matrice și sunt sortate.
deci, o condiție necesară pentru căutarea binară este ca lista/matricea să fie sortată.
caracteristici de căutare binare
- este mare pentru a căuta prin matrice sortate mari.
- are o complexitate temporală de O(log n) care este o complexitate temporală foarte bună. Vom discuta acest lucru în detaliu în tutorialul de căutare binară.
- are o implementare simplă.