Binarno pretraživanje u odnosu na linearno pretraživanje
Linearno pretraživanje, poznato i kao sekvencijalno pretraživanje, najjednostavniji je algoritam pretraživanja. Traži određenu vrijednost na popisu provjeravanjem svakog elementa na popisu. Binarno pretraživanje također je metoda koja se koristi za lociranje određene vrijednosti na sortiranom popisu. Metoda binarnog pretraživanja prepolovljuje broj provjerenih elemenata (u svakoj iteraciji), smanjujući vrijeme potrebno za lociranje dane stavke na popisu.
Što je linearno pretraživanje?
Linearno pretraživanje je najjednostavnija metoda pretraživanja, koja uzastopno provjerava svaki element na popisu dok ne pronađe određeni element. Ulaz u linearnu metodu pretraživanja je niz (kao što je niz, zbirka ili niz) i stavka koju je potrebno pretražiti. Izlaz je istinit ako je navedena stavka unutar navedenog niza ili lažan ako nije u nizu. Budući da ova metoda provjerava svaku stavku na popisu dok se navedena stavka ne pronađe, u najgorem slučaju proći će kroz sve elemente na popisu prije nego što pronađe traženi element. Složenost linearne pretrage je o(n). Stoga se smatra da je prespor za korištenje pri pretraživanju elemenata u velikim popisima. Ali ovo je vrlo jednostavno i lakše za implementirati.
Što je binarno pretraživanje?
Binarno pretraživanje također je metoda koja se koristi za lociranje određene stavke na sortiranom popisu. Ova metoda počinje usporedbom traženog elementa s elementima u sredini popisa. Ako se usporedbom utvrdi da su dva elementa jednaka, metoda se zaustavlja i vraća položaj elementa. Ako je traženi element veći od srednjeg elementa, ponovno pokreće metodu koristeći samo donju polovicu sortiranog popisa. Ako je traženi element manji od srednjeg elementa, ponovno pokreće metodu koristeći samo gornju polovicu sortiranog popisa. Ako traženi element nije unutar popisa, metoda će vratiti jedinstvenu vrijednost koja to pokazuje. Stoga metoda binarnog pretraživanja prepolovljuje broj uspoređivanih elemenata (u svakoj iteraciji), ovisno o rezultatu usporedbe. Posljedično, binarno pretraživanje radi u logaritamskom vremenu što rezultira o(log n) prosječnom izvedbom velikih i malih slova.
Koja je razlika između binarnog i linearnog pretraživanja?
Iako su i linearno pretraživanje i binarno pretraživanje metode pretraživanja, one imaju nekoliko razlika. Dok binarno pretraživanje radi na sortiranim popisima, liner pretraživanje može raditi i na nesortiranim popisima. Sortiranje popisa općenito ima prosječnu složenost slučajeva od n log n. linearno pretraživanje je jednostavno i jednostavno implementirati od binarnog pretraživanja. Ali linearno pretraživanje je presporo da bi se koristilo s velikim popisima zbog o(n) prosječnih performansi velikih i malih slova. S druge strane, binarno pretraživanje smatra se učinkovitijom metodom koja se može koristiti s velikim popisima. Ali implementacija binarnog pretraživanja mogla bi biti prilično nezgodna i studija je pokazala da se točan kod za binarno pretraživanje može pronaći u samo pet od dvadeset knjiga.
