Algoritam binarnog pretraživanja s PRIMJEROM

Prije nego što naučimo binarno pretraživanje, naučimo:

Što je Search?

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 spajanja kriterija sa zapisima i njihovog prikazivanja korisniku. Na taj način funkcionira najosnovnija funkcija pretraživanja.

Što je binarno pretraživanje?

Binarno pretraživanje je napredna vrsta algoritma pretraživanja koji pronalazi i dohvaća podatke s sortiranog popisa stavki. Njegov temeljni princip rada uključuje dijeljenje podataka na popisu na pola dok se tražena vrijednost ne pronađe i prikaže korisniku u rezultatima pretraživanja. Binarno pretraživanje je općenito poznato kao a poluintervalna pretraga ili logaritamsko pretraživanje.

Kako radi binarno pretraživanje?

Binarno pretraživanje radi na sljedeći način:

• Proces pretraživanja započinje lociranjem srednjeg elementa sortiranog niza podataka
• Nakon toga se ključna vrijednost uspoređuje s elementom
• Ako je vrijednost ključa manja od srednjeg elementa, pretraživanje analizira gornje vrijednosti srednjeg elementa za usporedbu i podudaranje
• U slučaju da je ključna vrijednost veća od srednjeg elementa, tada pretraživanja analiziraju niže vrijednosti srednjeg elementa za usporedbu i podudaranje

Primjer binarnog pretraživanja

Pogledajmo primjer rječnika. Ako trebate pronaći određenu riječ, nitko ne prolazi kroz svaku riječ u nizu, već nasumično locira najbliže riječi za traženje tražene riječi.

Gornja slika ilustrira sljedeće:

1. Imate niz od 10 znamenki, a potrebno je pronaći element 59.
2. Svi elementi su označeni indeksom od 0 – 9. Sada se izračunava sredina niza. Da biste to učinili, uzmete lijevu i krajnju desnu vrijednost indeksa i podijelite ih s 2. Rezultat je 4.5, ali uzimamo donju vrijednost. Stoga je sredina 4.
3. Algoritam ispušta sve elemente od sredine (4) do najniže granice jer je 59 veće od 24, i sada u nizu ostaje samo 5 elemenata.
4. Sada je 59 veće od 45 i manje od 63. Sredina je 7. Dakle, vrijednost desnog indeksa postaje srednja – 1, što je jednako 6, a vrijednost lijevog indeksa ostaje ista kao prije, a to je 5.
5. U ovom trenutku znate da 59 dolazi nakon 45. Stoga, lijevi indeks, koji je 5, također postaje srednji.
6. Te se iteracije nastavljaju sve dok se niz ne smanji na samo jedan element ili stavka koju treba pronaći postane sredina niza.

Primjer 2

Pogledajmo sljedeći primjer kako bismo razumjeli funkcioniranje binarnog pretraživanja

1. Imate niz razvrstanih vrijednosti u rasponu od 2 do 20 i trebate pronaći 18.
2. Prosjek donje i gornje granice je (l + r) / 2 = 4. Vrijednost koja se pretražuje veća je od sredine koja je 4.
3. Vrijednosti niza manje od sredine ispuštaju se iz pretraživanja, a pretražuju se vrijednosti veće od srednje vrijednosti 4.
4. Ovo je ponavljajući proces dijeljenja sve dok se ne pronađe stvarna stavka koju treba pretražiti.

Zašto nam treba binarno pretraživanje?

Sljedeći razlozi čine binarno pretraživanje boljim izborom za korištenje kao algoritam pretraživanja:

• Binarno pretraživanje učinkovito radi na sortiranim podacima bez obzira na veličinu podataka
• Umjesto izvođenja pretraživanja prolaskom kroz niz podataka, binarni algoritam nasumično pristupa podacima kako bi pronašao traženi element. Time su ciklusi pretraživanja kraći i točniji.
• Binarno pretraživanje izvodi usporedbe razvrstanih podataka na temelju načela sređivanja nego korištenjem usporedbi jednakosti, koje su sporije i uglavnom netočne.
• Nakon svakog ciklusa pretraživanja, algoritam dijeli veličinu niza na pola pa će u sljedećoj iteraciji raditi samo u preostaloj polovici niza.

Naučite naš sljedeći vodič za Linearno pretraživanje: Python, C++ Primjer

Rezime

• Pretraživanje je uslužni program koji korisniku omogućuje pretraživanje dokumenata, datoteka i drugih vrsta podataka. Binarno pretraživanje je napredna vrsta algoritma pretraživanja koji pronalazi i dohvaća podatke s sortiranog popisa stavki.
• Binarno pretraživanje općenito je poznato kao poluintervalno pretraživanje ili logaritamsko pretraživanje
• Funkcionira dijeljenjem niza na pola pri svakoj iteraciji ispod traženog elementa.
• The binarni algoritam uzima sredinu niza dijeljenjem zbroja vrijednosti indeksa s lijeve i desne strane s 2. Sada, algoritam ispušta donju ili gornju granicu elemenata iz sredine niza, ovisno o elementu koji treba pronaći.
• Algoritam nasumično pristupa podacima kako bi pronašao traženi element. Time su ciklusi pretraživanja kraći i točniji.
• Binarno pretraživanje izvodi usporedbe razvrstanih podataka na temelju načela sređivanja umjesto usporedbi jednakosti koje su spore i netočne.
• Binarno pretraživanje nije prikladno za nesortirane podatke.