Razlika između binarne pretraživanja i linearne pretrage

Binarna pretraga vs Linearna pretraga

Linearna pretraga, poznata i kao sekvencijalna pretraga, najjednostavniji je algoritam pretraživanja. Traži određenu vrijednost na popisu provjeravajući svaki element na popisu. Binarna pretraga je također metoda koja se koristi za pronalaženje određene vrijednosti na razvrstanom popisu. Binarna metoda pretraživanja prepolovi broj provjerenih elemenata (u svakoj iteraciji), smanjujući vrijeme potrebno za pronalazak određene stavke na popisu.

Što je linearno pretraživanje?

Linearno pretraživanje najjednostavnija je metoda pretraživanja koja svaki element na popisu provjerava uzastopno dok ne nađe zadani element. Ulaz u metodu linearnog pretraživanja je redoslijed (kao što su niz, zbirka ili niz) i stavka koju je potrebno pretraživati. 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 ne bude pronađena navedena stavka, u najgorem slučaju će proći sve elemente na popisu prije nego što pronađe potreban element. Složenost linearnog pretraživanja je o (n). Stoga se smatra presporim da bi se koristio pri pretraživanju elemenata na velikim popisima. Ali to je vrlo jednostavno i lakše provoditi.

Što je binarna pretraga?

Binarna pretraga je također metoda koja se koristi za pronalaženje određene stavke na razvrstanom popisu. Ova metoda započinje usporedbom pretraživanog elementa s elementima na sredini popisa. Ako usporedba utvrdi da su dva elementa jednaka, metoda se zaustavlja i vraća položaj elementa. Ako je pretraživani element veći od srednjeg elementa, ponovo započinje metodu koristeći samo donju polovicu popisa. Ako je pretraživani element manji od srednjeg elementa, ponovo započinje metodu koristeći samo gornju polovicu poredanog popisa. Ako pretraživani element nije na popisu, metoda će vratiti jedinstvenu vrijednost koja to ukazuje. Stoga metoda binarnog pretraživanja prepolovljuje broj uspoređenih elemenata (u svakoj iteraciji), ovisno o rezultatu usporedbe. Prema tome, binarna pretraga radi u logaritamskom vremenu što rezultira o (log n) prosječnim performansama slučaja.

Koja je razlika između binarnog pretraživanja i linearnog pretraživanja?

Iako su i linearno i binarno pretraživanje metode pretraživanja, postoje nekoliko razlika. Dok binarna pretraga radi na sortiranim popisima, pretraživanje linijskih linija može raditi i na poništenim popisima. Poredavanje popisa općenito ima prosječnu složenost slučaja n log n. linearno pretraživanje jednostavno je i jednostavno izvesti od binarnog pretraživanja. No, linearno pretraživanje presporo je da bi se koristilo na velikim popisima zbog svog (n) prosječnog učinka. S druge strane, binarna pretraga smatra se učinkovitijom metodom koja se može koristiti s velikim popisima. No, implementacija binarnog pretraživanja mogla bi biti prilično škakljiva, a istraživanje je pokazalo da je točan kôd za binarno pretraživanje moguće pronaći u samo pet od dvadeset knjiga.