Prije nego što naučimo binarno pretraživanje, naučimo:
Što je pretraživanje?
Pretraživanje je uslužni program koji korisniku omogućuje pronalaženje dokumenata, datoteka, medija ili bilo koje druge vrste podataka koji se nalaze u bazi podataka. Pretraživanje radi na jednostavnom principu podudaranja kriterija sa zapisima i prikazivanja korisniku. Na taj način funkcionira najosnovnija funkcija pretraživanja.
Što je binarno pretraživanje?
Binarno pretraživanje napredna je vrsta algoritma pretraživanja koja pronalazi i dohvaća podatke sa razvrstanog popisa stavki. Njegov osnovni princip rada uključuje podjelu podataka s popisa na pola dok se tražena vrijednost ne pronađe i ne prikaže korisniku u rezultatu pretraživanja. Binarno pretraživanje obično je poznato kao pretraživanje s pola intervala ili logaritamsko pretraživanje .
U ovom uputstvu iz algoritma naučit ćete:
- Što je pretraživanje?
- Što je binarno pretraživanje?
- Kako binarno pretraživanje djeluje?
- Primjer binarnog pretraživanja
- Zašto nam je potrebna binarna pretraga?
Kako binarno pretraživanje djeluje?
Binarno pretraživanje radi na sljedeći način:
- Proces pretraživanja započinje lociranjem srednjeg elementa razvrstanog niza podataka
- Nakon toga se vrijednost ključa uspoređuje s elementom
- Ako je vrijednost ključa manja od srednjeg elementa, pretraživanjem se analiziraju gornje vrijednosti srednjeg elementa radi usporedbe i podudaranja
- U slučaju da je vrijednost ključa veća od srednjeg elementa, pretraga analizira niže vrijednosti srednjeg elementa radi usporedbe i podudaranja
Primjer binarnog pretraživanja
Pogledajmo primjer rječnika. Ako trebate pronaći određenu riječ, nitko ne prolazi kroz svaku riječ u slijedu, već nasumce pronalazi najbliže riječi kako bi potražio potrebnu riječ.
Gornja slika ilustrira sljedeće:
- Imate niz od 10 znamenki, a element 59 treba pronaći.
- Svi su elementi označeni indeksom od 0 - 9. Izračunava se sredina niza. Da biste to učinili, uzimate lijevu i desnu vrijednost indeksa i dijelite ih s 2. Rezultat je 4,5, ali mi uzimamo najnižu vrijednost. Stoga je sredina 4.
- Algoritam spušta sve elemente od srednje (4) do najniže granice jer je 59 veće od 24, a sada je u nizu ostalo samo 5 elemenata.
- Sada je 59 veće od 45, a manje od 63. Sredina je 7. Stoga vrijednost desnog indeksa postaje srednja - 1, što je jednako 6, a lijeva vrijednost indeksa ostaje ista kao i prije, što je 5.
- U ovom trenutku znate da 59 dolazi nakon 45. Stoga i lijevi indeks, koji je 5, postaje srednji.
- Te se iteracije nastavljaju sve dok se niz ne smanji na samo jedan element ili dok stavka koju treba pronaći postane sredina niza.
Primjer 2
Pogledajmo sljedeći primjer da bismo razumjeli kako funkcionira binarno pretraživanje
- Imate niz sortiranih vrijednosti u rasponu od 2 do 20 i trebate locirati 18.
- Prosjek donje i gornje granice je (l + r) / 2 = 4. Tražena vrijednost veća je od sredine koja iznosi 4.
- Vrijednosti polja manje od sredine ispuštaju se iz pretraživanja i pretražuju se vrijednosti veće od srednje vrijednosti 4.
- Ovo je ponavljajući postupak dijeljenja dok se ne pronađe stvarna stavka koju treba pretražiti.
Zašto nam je potrebna binarna pretraga?
Sljedeći razlozi čine binarno pretraživanje boljim izborom koji će se koristiti kao algoritam pretraživanja:
- Binarno pretraživanje učinkovito djeluje na razvrstanim podacima bez obzira na veličinu podataka
- Umjesto da pretražujući prolazi niz podataka u nizu, binarni algoritam nasumce pristupa podacima kako bi pronašao potreban element. To čini cikluse pretraživanja kraćim i preciznijim.
- Binarno pretraživanje vrši usporedbe razvrstanih podataka na temelju principa poredavanja nego upoređivanje jednakosti, koje su sporije i uglavnom netočne.
- Nakon svakog ciklusa pretraživanja, algoritam dijeli veličinu polja na pola, dakle u sljedećoj iteraciji će raditi samo na preostaloj polovici polja
Sažetak
- Pretraživanje je uslužni program koji korisniku omogućuje pretraživanje dokumenata, datoteka i drugih vrsta podataka. Binarno pretraživanje napredna je vrsta algoritma pretraživanja koja pronalazi i dohvaća podatke sa razvrstanog popisa stavki.
- Binarno pretraživanje obično je poznato kao pretraživanje s pola intervala ili logaritamsko pretraživanje
- Djeluje dijeljenjem niza na polovice na svakoj iteraciji ispod traženog elementa.
- Binarni algoritam uzima sredinu niza dijeleći zbroj lijeve i krajnje desne vrijednosti indeksa s 2. Sada algoritam spušta ili donju ili gornju granicu elemenata sa sredine niza, ovisno o elementu koji treba pronaći .
- Algoritam nasumce pristupa podacima kako bi pronašao traženi element. To čini cikluse pretraživanja kraćim i preciznijim.
- Binarno pretraživanje vrši usporedbe razvrstanih podataka na temelju principa poredavanja nego pomoću uspoređivanja jednakosti koje su spore i netočne.
- Binarno pretraživanje nije prikladno za nerazvrstane podatke.