Binary Search vs Linear Search
Linearna pretraga, poznata i kao sekvencijalna pretraga je najjednostavniji algoritam pretraživanja. On traži određenu vrijednost na listi provjeravanjem svakog elementa na listi. Binarno pretraživanje je također metoda koja se koristi za lociranje određene vrijednosti u sortiranoj listi. Metoda binarnog pretraživanja prepolovi broj provjerenih elemenata (u svakoj iteraciji), smanjujući vrijeme potrebno za lociranje date stavke na listi.
Šta je linearna pretraga?
Linearna pretraga je najjednostavniji metod pretraživanja, koji provjerava svaki element na listi uzastopno dok ne pronađe određeni element. Ulaz za metod linearne pretrage je niz (kao što je niz, kolekcija ili niz) i stavka koju treba pretražiti. Izlaz je istinit ako je navedena stavka unutar navedenog niza ili lažan ako nije u nizu. Pošto ova metoda provjerava svaku stavku na listi dok se navedena stavka ne pronađe, u najgorem slučaju će proći kroz sve elemente na listi prije nego što pronađe traženi element. Složenost linearne pretrage je o(n). Stoga se smatra da je presporo da bi se koristilo prilikom pretraživanja elemenata u velikim listama. Ali ovo je vrlo jednostavno i lakše za implementaciju.
Šta je binarno pretraživanje?
Binarna pretraga je takođe metoda koja se koristi za lociranje određene stavke u sortiranoj listi. Ova metoda počinje poređenjem traženog elementa sa elementima u sredini liste. Ako poređenje utvrdi da su dva elementa jednaka, metoda se zaustavlja i vraća poziciju elementa. Ako je traženi element veći od srednjeg elementa, on ponovo pokreće metodu koristeći samo donju polovinu sortirane liste. Ako je traženi element manji od srednjeg elementa, on ponovo pokreće metodu koristeći samo gornju polovinu sortirane liste. Ako se traženi element ne nalazi na listi, metoda će vratiti jedinstvenu vrijednost koja to ukazuje. Stoga metoda binarnog pretraživanja prepolovi broj upoređenih elemenata (u svakoj iteraciji), u zavisnosti od rezultata poređenja. Posljedično, binarno pretraživanje radi u logaritamskom vremenu što rezultira o(log n) prosječnim performansama velikih i malih slova.
Koja je razlika između binarnog i linearnog pretraživanja?
Iako su i linearna pretraga i binarna pretraga metode pretraživanja, one imaju nekoliko razlika. Dok binarno pretraživanje radi na sortiranim listama, linijsko pretraživanje može raditi i na nesortiranim listama. Sortiranje liste općenito ima prosječnu složenost slučaja od n log n. linearno pretraživanje je jednostavno i jednostavno za implementaciju od binarnog pretraživanja. Ali, linearna pretraga je prespora da bi se koristila sa velikim listama zbog o(n) prosečnih performansi velikih i malih slova. S druge strane, binarno pretraživanje se smatra efikasnijom metodom koja se može koristiti sa velikim listama. Ali implementacija binarnog pretraživanja mogla bi biti prilično nezgodna i studija je pokazala da se tačan kod za binarno pretraživanje može naći u samo pet od dvadeset knjiga.
