Razlika Između Binarnog Pretraživanja I Linearnog Pretraživanja

2024 Autor: Mildred Bawerman | [email protected]. Zadnja promjena: 2023-12-16 08:39

Binarno pretraživanje vs Linearno pretraživanje

Linearno pretraživanje, poznato i kao sekvencijalno pretraživanje, najjednostavniji je algoritam pretraživanja. Traži navedenu vrijednost na popisu provjerom svakog elementa na popisu. Binarno pretraživanje također je metoda koja se koristi za pronalaženje određene vrijednosti na razvrstanom popisu. Binarna metoda pretraživanja prepolovljuje broj provjerenih elemenata (u svakoj iteraciji), smanjujući vrijeme potrebno za pronalaženje zadane stavke na popisu.

Što je linearno pretraživanje?

Linearno pretraživanje najjednostavnija je metoda pretraživanja koja uzastopno provjerava svaki element na popisu dok ne pronađe navedeni element. Ulaz u metodu linearnog pretraživanja je niz (poput niza, zbirke ili niza) i stavka koju treba pretražiti. Izlaz je istinit ako je navedena stavka unutar predviđenog niza ili lažan ako nije u nizu. Budući da ova metoda provjerava svaku stavku na popisu dok se ne pronađe navedena stavka, u najgorem slučaju proći će sve elemente na popisu prije nego što pronađe traženi element. Složenost linearnog pretraživanja je o (n). Stoga se smatra presporim za upotrebu prilikom pretraživanja elemenata na velikim popisima. Ali ovo je vrlo jednostavno i jednostavnije za provedbu.

Što je binarno pretraživanje?

Binarno pretraživanje također je metoda koja se koristi za pronalaženje određene stavke na razvrstanom popisu. Ova metoda započinje usporedbom pretraživanog elementa s elementima u sredini popisa. Ako usporedba 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, on ponovno započinje metodu koristeći samo donju polovicu razvrstanog popisa. Ako je pretraživani element manji od srednjeg elementa, on ponovno započinje metodu koristeći samo gornju polovicu razvrstanog popisa. Ako se pretraženi element ne nalazi na popisu, metoda će vratiti jedinstvenu vrijednost koja to pokazuje. Stoga binarna metoda pretraživanja prepolovljuje broj uspoređenih elemenata (u svakoj iteraciji), ovisno o rezultatu usporedbe. Slijedom toga,binarno pretraživanje radi u logaritamskom vremenu što rezultira o (log n) prosječnom izvedbom 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, oni imaju nekoliko razlika. Dok binarno pretraživanje djeluje na razvrstanim popisima, linijsko pretraživanje može raditi i na nesortiranim popisima. Sortiranje popisa obično ima prosječnu složenost slova od n log n. linearno pretraživanje jednostavno je i jednostavno za provedbu od binarnog pretraživanja. Ali, linearno je pretraživanje presporo da bi se koristilo s velikim popisima zbog svoje prosječne izvedbe slučaja o (n). S druge strane, binarno pretraživanje smatra se učinkovitijom metodom koja se može koristiti s velikim popisima. No provedba binarnog pretraživanja mogla bi biti prilično nezgodna, a studija je pokazala da se točan kod binarnog pretraživanja može naći u samo pet od dvadeset knjiga.