Binarna pretraga

Binarna pretraga

Binarno petraživački niz
Klasa	Algoritam sortiranja
Struktura podataka	Niz
Najgora performanca	$O(logn)$
Najbolja performanca	$O(logn)$
Najgora prostorna kompleksnost	$O(n)$

U računarstvu, binarna pretraga ili pretraga metodom polovljenih intervala je algoritam pronalaženja indeksa određenog elementa - ključa u sortiranom nizu. U svakom koraku, algoritam upoređuje vrednost ključa (vrednost koju se traži) sa vrednošću središnjeg člana niza. Ukoliko se vrednosti podudaraju, algoritam se završava, u suprotnom, ukoliko je vrednost ključa manja od vrednosti središnjeg člana algoritam se ponavlja na levi podniz u odnosu na središnji element. Ako je ključ veći od središnjeg člana onda se algoritam primenjuje na desni podniz. Ovaj proces se ponavlja sve dok ključ nije nađen, ili dok podniz ne postane prazan, što znači da se ključ ne nalazi u nizu.

Binarna pretraga u najgorem slučaju poseduje logaritamsku vremensku složenost, radeći $O(\log n)$ poređenja gde je $n$ broj elemenata u nizu.

Algoritam

Binarna pretraga radi na sortiranom nizu. Počinje tako što se upoređuje element u sredini niza sa traženom vrednošću. Ako je traženi element jednak izabranom elementu vraća se njegova indeks u nizu. Ako je tražena vrednost manja od izabranog elementa, pretraga se nastavlja na donjoj polivini niza. Ako je tražena vrednost veća od izabranog elementa, pretraga se nastavlja na gornjoj polivini niza. Ovako, u svakoj iteraciji, algoritam eliminiše polovinu niza u kom traženi element ne može biti.

Procedura

Za dati niz $A$ koji se sastoji od $n$ elemenata sa vrednostima $A_{0},A_{1},A_{2},\ldots ,A_{n-1}$ sortirani tako da $A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}$ i traženu vrednost $T$, sledeća podrutina koristi binarnu pretragu da nađe indeks $T$ u nizu $A$

1. Postaviti da je $L$ jedanako $0$ i da je $R$ jednako $n-1$.
2. Ako je $L>R$, pretraga se zaustavlja kao neuspešna.
3. Postaviti $m$ (poziciju srednjeg elementa) da bude jednako floor funkciji vrednosti ${\frac {L+R}{2}}$.
4. Ako je $A_{m}<T$, postaviti $L$ da bude jednako $m+1$ pa otići na korak 2.
5. Ako je $A_{m}>T$, postaviti $R$ da bude jednako $m-1$ pa otići na korak 2.
6. $A_{m}=T$ pretraga je gotova i vraća se $m$.

Ova iterativna procedura prati granice pretrage sa dve promenljive $L$ i $R$. Procedura može biti predstavljena u sledećem pseudokodu, u kom su promeljive imenovane kao u pre napomenutoj proceduri, gde neuspeh predstavlja vrednost koja označava neuspeh pretrage.

Binarna pretraga

function binarna_pretraga(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return neuspeh

Performanse

U svakom testu koji ne uspe da pronađe traženi ključ, pretraga se nastavlja u jednom ili drugom podintervalu koji je duplo manji po veličini od polaznog. Tačnije, ukoliko je veličina pokaznog intevala N , tada podintevali sadrže po N/2 ili N/2-1 elemenata.

Posle prve iteracije niz koji pretražujemo ima najviše N/2 članova. U narednoj, N/4 i tako dalje. U najgorem slučaju, ako se u nizu ne nalazi vrednost ključa algoritam mora da nastavi pretragu sve dok ne dobije prazan podniz. U najgorem slučaju, to će se dogoditi za ⌊log_2⁡〖n+1〗 ⌋ koraka. Gde je ⌊h⌋ notacija koja argument h zaokružuje na prvi manji ceo broj. U odnosu na lineranu pretragu, čija je u najgorem slučaju, složenost od N iteracija. Primećujemo da je binarna pretraga znatno brža od linearne. Na primer, ukoliko pretražujemo niz od milion članova, u linearnoj pretrazi bismo imali isto toliko koraka, a u binarnoj pretrazi nikad više od dvadeset iteracija. Mana binarne pretrage je u tome što se ovim algoritmom ne može pretražiti niz koji nije sotriran.

Literatura

• Tomašević, Milo (2008). „1”. Algoritmi i strukture podataka (1st izd.). Beograd: Akademska misao. str. 406. ISBN 978-86-7466-328--8. Pristupljeno 09. 02. 2016. „Složenost algoritama” 
• Škarić, Milan; Viktor, Radović (2009). „5”. Uvod u programiranje (prvo izd.). Beograd: Mikro knjiga. str. 205. ISBN 978-86-7555-349-6. Pristupljeno 09. 02. 2016. „Pretraga niza” 
• Introductions to algorithms -Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein, knjigu možete pogledati ovde Arhivirano na sajtu Wayback Machine (18. oktobar 2016)
• Algoritmi i strukture podataka - Milo Tomašević
• Uvod u programiranje - Milan Škarić
• Alexandrescu, Andrei (2010). The D Programming Language. Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-63536-5. 
• Bentley, Jon (2000) [1986]. Programming Pearls (2nd izd.). Addison-Wesley. ISBN 978-0-201-65788-3. 
• Chang, Shi-Kuo (2003). Data Structures and Algorithms. Software Engineering and Knowledge Engineering. 13. Singapore: World Scientific. ISBN 978-981-238-348-8. 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd izd.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. 
• Fitzgerald, Michael (2007). Ruby Pocket Reference. Sebastopol, CA: O'Reilly Media. ISBN 978-1-4919-2601-7. 
• Goldman, Sally A.; Goldman, Kenneth J. (2008). A Practical Guide to Data Structures and Algorithms using Java. Boca Raton: CRC Press. ISBN 978-1-58488-455-2. 
• Leiss, Ernst (2007). A Programmer's Companion to Algorithm Analysis. Boca Raton, FL: CRC Press. ISBN 978-1-58488-673-0. 
• Moffat, Alistair; Turpin, Andrew (2002). Compression and Coding Algorithms. Hamburg, Germany: Kluwer Academic Publishers. ISBN 978-0-7923-7668-2. doi:10.1007/978-1-4615-0935-6. 
• Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (4th izd.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-57351-3. 
• Stroustrup, Bjarne (2013). The C++ Programming Language (4th izd.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-56384-2.