Binarna pretraga

Sadržaj

• Definicija - Što znači Binarna pretraga?
• Uvod u Microsoft Azure i Microsoft Cloud | Kroz ovaj vodič naučit ćete o čemu se radi računalstvo u oblaku i kako vam Microsoft Azure može pomoći da preselite i pokrenete svoje poslovanje iz oblaka.
• Tehopedija objašnjava Binarnu pretragu

Definicija - Što znači Binarna pretraga?

Algoritam binarnog pretraživanja koristi se za pronalaženje položaja određene vrijednosti sadržane u razvrstanom nizu. Radeći s principom dijeljenja i osvajanja, ovaj algoritam pretraživanja može biti vrlo brz, ali upozorenje je da podaci moraju biti u sortiranom obliku. Djeluje tako što započinje pretraživanje u sredini niza i nastavlja spuštanjem prve donje ili gornje polovice niza. Ako je srednja vrijednost niža od ciljane vrijednosti, to znači da pretraga mora ići i više, ako ne, treba gledati na silazni dio matrice.

Binarna pretraga poznata je i kao pretraživanje u pola intervala ili logaritamska pretraga.

Uvod u Microsoft Azure i Microsoft Cloud | Kroz ovaj vodič naučit ćete o čemu se radi računalstvo u oblaku i kako vam Microsoft Azure može pomoći da preselite i pokrenete svoje poslovanje iz oblaka.

Tehopedija objašnjava Binarnu pretragu

Binarna pretraga brza je i učinkovita metoda pronalaska određene ciljne vrijednosti iz skupa naručenih predmeta. Počevši na sredini poredanog popisa, može učinkovito smanjiti prostor za pretraživanje na pola određivanjem hoće li se uzdići ili spustiti popis na temelju srednje vrijednosti u odnosu na ciljanu vrijednost.

Na primjer, s ciljanom vrijednošću 8 i prostorom za pretraživanje od 1 do 11:

1. Pronađena je srednja / srednja vrijednost i tamo je postavljen pokazivač, koji je u ovom slučaju 6.
2. Cilj 8 uspoređuje se s 6. Budući da je 6 manje od 8, cilj mora biti u gornjoj polovici.
3. Pokazivač se pomiče na sljedeću vrijednost (7) i uspoređuje s ciljem. Manje je, pa se pokazivač prelazi na sljedeću veću vrijednost.
4. Pokazivač je sada na 8. Ako usporedimo to s ciljem, to je točno podudaranje, pa je cilj pronađen.

Koristeći binarno pretraživanje, cilj se morao usporediti samo s tri vrijednosti. U usporedbi s linearnim pretraživanjem, ono bi počelo od prve vrijednosti i pomaknulo se prema gore, trebalo bi usporediti cilj s osam vrijednosti. Binarno pretraživanje moguće je samo s naručenim skupom podataka; ako su podaci nasumično raspoređeni, tada bi linearna pretraga dala rezultate cijelo vrijeme dok bi se binarna pretraga vjerojatno zaglavila u beskonačnoj petlji.