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. Acesta caută o valoare specificată într-o listă verificând fiecare element din listă. Căutarea binară este, de asemenea, o metodă folosită pentru a localiza o valoare specificată într-o listă sortată. Metoda de căutare binară reduce la jumătate 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ă secvențial fiecare element dintr-o listă până când găsește un element specificat. Intrarea în metoda de căutare liniară este o secvență (cum ar fi o matrice, o colecție sau un șir) și elementul care trebuie căutat. Rezultatul este adevărat dacă elementul specificat se află în secvența furnizată sau fals dacă nu este în secvența. Deoarece această metodă verifică fiecare element din listă până când este găsit elementul specificat, în cel mai rău caz va parcurge 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 căutarea binară?
Căutarea binară este, de asemenea, o metodă folosită pentru a localiza un articol specificat într-o listă sortată. Această metodă începe prin a compara elementul 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, reîncepe metoda folosind doar jumătatea de jos a listei sortate. Dacă elementul căutat este mai mic decât elementul din mijloc, reîncepe 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ă reduce la jumătate numărul de elemente comparate (în fiecare iterație), în funcție de rezultatul comparației. În consecință, căutarea binară rulează în timp logaritmic, rezultând o performanță medie a cazurilor (log n).
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ă operează pe liste sortate, căutarea pe linie poate opera și pe liste nesortate. Sortarea unei liste are în general o complexitate medie a cazurilor de n log n. căutarea liniară este simplu și simplu 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 la o (n) cazuri. 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 în doar cinci din douăzeci de cărți.
