Algoritam binarnog pretraživanja s PRIMJEROM

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

Š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 osnovni princip rada uključuje dijeljenje podataka na popisu na pola dok se ne pronađe tražena vrijednost i ne prikaže korisniku u rezultatu pretraživanja. Binarno pretraživanje je općenito poznato kao 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, ključna vrijednost se uspoređuje s elementom.
• Ako je ključna vrijednost manja od srednjeg elementa, tada pretraga analizira gornje vrijednosti do srednjeg elementa radi usporedbe i podudaranja.
• U slučaju da je ključna vrijednost veća od srednjeg elementa, pretraga analizira niže vrijednosti srednjeg elementa radi usporedbe i podudaranja.

Binarni algoritam pretraživanja (pseudokod)

Binarno pretraživanje može se napisati kao kratka, iterativna rutina. Zadržava dva pokazivača, niski i visoki, i sužava raspon dok se cilj ne pronađe ili raspon ne postane prazan.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

Rutina vraća indeks cilja u slučaju uspjeha i -1 kada vrijednost nije prisutna. Budući da se raspon prepolovi pri svakom prolazu, petlja se izvršava najviše log₂(n) puta.

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 do 9. Sada se izračunava sredina niza. Da biste to učinili, uzimate lijevu i krajnju desnu vrijednost indeksa i dijelite ih s 2. Rezultat je 4.5, ali uzimamo donju vrijednost. Stoga je sredina 4.
3. Algoritam izostavlja sve elemente od sredine (4) do donje granice, jer je 59 veće od 24, i sada niz ostaje samo s 5 elemenata.
4. Sada je 59 veće od 45 i manje od 63. Sredina je 7. Stoga desna vrijednost indeksa postaje srednja -1, što je jednako 6, a lijeva vrijednost indeksa ostaje ista kao i prije, š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 kako funkcionira binarno pretraživanje.

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 traži veća je od srednje vrijednosti, koja je 4.
3. Vrijednosti polja manje od sredine se izostavljaju iz pretrage, 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 uspoređuje sortirane podatke na temelju načela uređenja, umjesto korištenja usporedbi jednakosti, koje su sporije i uglavnom netočne.
• Nakon svakog ciklusa pretraživanja, algoritam dijeli veličinu polja na pola; stoga će u sljedećoj iteraciji raditi samo u preostaloj polovici polja.

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

Binarno pretraživanje u odnosu na linearno pretraživanje

Binarno pretraživanje i linearno pretraživanje dva su najčešća načina pronalaženja vrijednosti u kolekciji. Tablica u nastavku ističe kako se razlikuju:

Ukratko, binarno pretraživanje je puno brže na velikim sortiranim podacima, dok je linearno pretraživanje jednostavnije i jedina je opcija kada podaci nisu sortirani.

Pitanja i odgovori