Căutare binară vs căutare liniară
Căutarea liniară, cunoscută și sub numele de căutare secvențială, este cel mai simplu algoritm de căutare. Se caută o valoare specificată într-o listă verificând fiecare element din listă. Căutarea binară este, de asemenea, o metodă utilizată pentru a localiza o valoare specificată într-o listă sortată. Metoda de căutare binară înjumătățește numărul de elemente verificate (în fiecare iterație), reducând timpul necesar pentru a localiza elementul dat în listă.
Ce este Căutarea liniară?
Căutarea liniară este cea mai simplă metodă de căutare, care verifică fiecare element dintr-o listă secvențial până când găsește un element specificat. Introducerea metodei de căutare liniară este o secvență (cum ar fi o matrice, o colecție sau un șir) și elementul care trebuie căutat. Ieșirea este adevărată dacă elementul specificat se află în secvența furnizată sau fals dacă nu se află în secvență. Deoarece această metodă verifică fiecare articol din listă până când elementul specificat este găsit, în cel mai rău caz va trece prin toate elementele din listă înainte de a găsi elementul necesar. Complexitatea căutării liniare este o (n). Prin urmare, este considerat a fi prea lent pentru a fi utilizat atunci când căutați elemente în liste mari. Dar acest lucru este foarte simplu și mai ușor de implementat.
Ce este Binary Search?
Căutarea binară este, de asemenea, o metodă utilizată pentru a localiza un element specificat într-o listă sortată. Această metodă începe prin compararea elementului căutat cu elementele din mijlocul listei. Dacă comparația determină că cele două elemente sunt egale, metoda se oprește și returnează poziția elementului. Dacă elementul căutat este mai mare decât elementul din mijloc, pornește din nou metoda folosind doar jumătatea de jos a listei sortate. Dacă elementul căutat este mai mic decât elementul din mijloc, pornește din nou metoda folosind doar jumătatea superioară a listei sortate. Dacă elementul căutat nu se află în listă, metoda va returna o valoare unică care indică acest lucru. Prin urmare, metoda de căutare binară înjumătățește numărul de elemente comparate (în fiecare iterație), în funcție de rezultatul comparației. Prin urmare,căutarea binară se execută în timp logaritmic rezultând o (log n) performanță medie a cazului.
Care este diferența dintre Căutarea binară și Căutarea liniară?
Chiar dacă atât căutarea liniară, cât și căutarea binară sunt metode de căutare, acestea au mai multe diferențe. În timp ce căutarea binară funcționează pe liste sortate, căutarea liner poate funcționa și pe liste nesortate. Sortarea unei liste are, în general, o complexitate medie a cazului n log n. căutarea liniară este simplă și simplă de implementat decât căutarea binară. Dar, căutarea liniară este prea lentă pentru a fi utilizată cu liste mari, datorită performanței sale medii de cazuri (o). Pe de altă parte, căutarea binară este considerată a fi o metodă mai eficientă care ar putea fi utilizată cu liste mari. Dar implementarea căutării binare ar putea fi destul de dificilă și un studiu a arătat că codul exact pentru căutarea binară ar putea fi găsit doar în cinci din douăzeci de cărți.
