Изворни код странице Бинарна претрага

{{Infobox Algorithm
|class   = [[Алгоритам сортирања]]<ref name="Низ">{{harvnb|Шкарић|2009|pp=205}}</ref>
|data    = [[Array data structure|Низ]]<ref name="Низ" />
|image   = [[Датотека:Binary Search Depiction.svg|200p]]
|caption = Бинарно петраживачки низ
|time    = <math>O(logn)</math><ref name="Комплексност">{{harvnb|Томашевић|2008|pp=406}}</ref>
|best-time = <math>O(logn)</math><ref name="Комплексност" />
|space   = <math>O(n)</math><ref name="Комплексност" />
}}
У рачунарству, '''бинарна претрага''' или ''претрага методом половљених интервала'' је [[алгоритам]] проналажења индекса одређеног елемента - кључа у [[Sortirani niz|сортираном низу]]. У сваком кораку, алгоритам упоређује вредност кључа (вредност коју се тражи) са вредношћу средишњег члана низа. Уколико се вредности подударају, алгоритам се завршава, у супротном, уколико је вредност кључа мања од вредности средишњег члана алгоритам се понавља на леви подниз у односу на средишњи елемент. Ако је кључ већи од средишњег члана онда се алгоритам примењује на десни подниз. Овај процес се понавља све док кључ није нађен, или док подниз не постане празан, што значи да се кључ не налази у низу.

Бинарна претрага у најгорем случају поседује логаритамску временску сложеност, радећи <math>O(\log n)</math> поређења где је <math>n</math> број елемената у низу.<ref name="FloresMadpis1971">{{cite journal|last1=Flores|first1=Ivan|last2=Madpis|first2=George|s2cid=43325465|title=Average binary search length for dense ordered lists|journal=[[Communications of the ACM]]|date=1 September 1971|volume=14|issue=9|pages=602–603|issn=0001-0782|doi=10.1145/362663.362752|doi-access=free}}</ref>

== Алгоритам ==
Бинарна претрага ради на сортираном низу. Почиње тако што се упоређује елемент у средини низа са траженом вредношћу. Ако је тражени елемент једнак изабраном елементу враћа се његова индекс у низу. Ако је тражена вредност мања од изабраног елемента, претрага се наставља на доњој поливини низа. Ако је тражена вредност већа од изабраног елемента, претрага се наставља на горњој поливини низа. Овако, у свакој итерацији, алгоритам елиминише половину низа у ком тражени елемент не може бити.

'''Процедура'''

За дати низ <math>A</math> који се састоји од <math>n</math> елемената са вредностима <math>A_0,A_1,A_2,\ldots,A_{n-1}</math> сортирани тако да <math>A_0 \leq A_1 \leq A_2 \leq \cdots \leq A_{n-1}</math>  и тражену вредност <math>T</math>, следећа [[подрутина]] користи бинарну претрагу да нађе индекс <math>T</math> у низу <math>A</math>{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), субсекција "History and bibliography"}}
# Поставити да је <math>L</math> једанако <math> 0</math> и да је <math>R</math> једнако <math>n-1</math>.
# Ако је <math>L>R</math>, претрага се зауставља као неуспешна.
# Поставити <math>m</math> (позицију средњег елемента) да буде једнако floor функцији{{efn|Функција која заокружује дати број на први цео број који је мањи или једнак датом броју (нпр. за 2.6 излаз би био 2)}} вредности <math>\frac{L+R}{2}</math>.
# Ако је <math>A_m < T</math>, поставити <math>L</math> да буде једнако <math>m+1</math> па отићи на корак 2.
# Ако је <math>A_m > T</math>, поставити <math>R</math> да буде једнако <math>m-1</math> па отићи на корак 2.
# <math>A_m = T</math> претрага је готова и враћа се <math>m</math>.
Ова итеративна процедура прати границе претраге са две променљиве <math>L</math> и <math>R</math>. Процедура може бити представљена у следећем [[Псеудокод|псеудокоду]], у ком су промељиве именоване као у пре напоменутој процедури, где <code>neuspeh</code> представља вредност која означава неуспех претраге.
[[File:Binary-search-work.gif|thumb|right|Бинарна претрага]]
 '''function''' binarna_pretraga(A, n, T) '''is'''
     L := 0
     R := n &minus; 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 &minus; 1
         '''else''':
             '''return''' m
     '''return''' neuspeh
== Перформансе ==
У сваком тесту који не успе да пронађе тражени кључ, претрага се наставља у једном или другом подинтервалу који је дупло мањи по величини од полазног. Тачније, уколико је величина показног интевала N , тада подинтевали садрже по N/2 или N/2-1 елемената.

После прве итерације низ који претражујемо има највише N/2 чланова. У наредној, N/4 и тако даље. У најгорем случају, ако се у низу не налази вредност кључа алгоритам мора да настави претрагу све док не добије празан подниз. У најгорем случају, то ће се догодити за ⌊log_2⁡〖n+1〗 ⌋ корака. Где је ⌊х⌋ нотација која аргумент х заокружује на први мањи [[цео број]]. У односу на линерану претрагу, чија је у најгорем случају, сложеност од N итерација. Примећујемо да је бинарна претрага знатно бржа од линеарне. На пример, уколико претражујемо низ од милион чланова, у [[линеарној претрази]] бисмо имали исто толико корака, а у бинарној претрази никад више од двадесет итерација. Мана бинарне претраге је у томе што се овим алгоритмом не може претражити низ који није сотриран.

== Напомене ==
{{notelist}}

== Референце ==
{{reflist}}

== Литература ==
{{Литература|30em}}
* {{Cite book| ref=harv|last=Томашевић|first=Мило|title=Алгоритми и структуре података|year=2008|publisher=Академска мисао|location=Београд|isbn=978-86-7466-328--8|url=http://akademska-misao.rs/ |edition=1st|accessdate=09. 02. 2016|language=Српски|chapter=1|quote=Сложеност алгоритама|pages=406}}
* {{Cite book| ref=harv|last=Шкарић|first=Милан|title=Увод у програмирање|year=2009|publisher=Микро књига|location=Београд|isbn=978-86-7555-349-6|url=http://www.mikroknjiga.rs |edition=прво| last2 = Виктор | first2 = Радовић |accessdate=09. 02. 2016|language=Српски|chapter=5|quote=Претрага низа|pages=205}}
* Introductions to algorithms -Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein, књигу можете погледати [http://bayanbox.ir/view/4177858657730907268/introduction-to-algorithms-3rd-edition.pdf овде] {{Wayback|url=http://bayanbox.ir/view/4177858657730907268/introduction-to-algorithms-3rd-edition.pdf |date=20161018163830 }}
* Алгоритми и структуре података - Мило Томашевић
* Увод у програмирање - Милан Шкарић
* {{Cite book| ref=harv|last=Alexandrescu|first=Andrei|title=The D Programming Language|year=2010|publisher=Addison-Wesley Professional|location=Upper Saddle River, NJ|isbn=978-0-321-63536-5}}
* {{Cite book| ref=harv|last=Bentley| first = Jon|authorlink= Jon Bentley (computer scientist)| title = Programming Pearls| edition = 2nd|publisher = [[Addison-Wesley]]|year=2000| origyear=1986|isbn=978-0-201-65788-3}}
* {{Cite book| ref=harv|last=Chang|first=Shi-Kuo|title=Data Structures and Algorithms | publisher=[[World Scientific]] |year=2003 | location=Singapore |isbn=978-981-238-348-8 | volume=13 | work=Software Engineering and Knowledge Engineering}}
* {{Introduction to Algorithms|edition=3|ref=harv}}
* {{Cite book| ref=harv|last=Fitzgerald|first=Michael|title=Ruby Pocket Reference|year=2007|publisher=[[O'Reilly Media]]|location=[[Sebastopol, California|Sebastopol, CA]]|isbn=978-1-4919-2601-7}}
* {{Cite book| ref=harv|last=Goldman|first=Sally A.|last2=Goldman|first2=Kenneth J.|title=A Practical Guide to Data Structures and Algorithms using Java|year=2008|publisher=[[CRC Press]]|location=Boca Raton|isbn=978-1-58488-455-2}}
* {{Cite book| ref=harv|last=Leiss|first=Ernst|title=A Programmer's Companion to Algorithm Analysis| url=https://archive.org/details/programmerscompa0000leis|year=2007|publisher=CRC Press|location=Boca Raton, FL|isbn=978-1-58488-673-0}}
* {{Cite book| ref=harv|last=Moffat|first=Alistair|last2=Turpin|first2=Andrew|title=Compression and Coding Algorithms| url=https://archive.org/details/compressioncodin0000moff|year=2002|publisher=Kluwer Academic Publishers|location=Hamburg, Germany|isbn=978-0-7923-7668-2|doi=10.1007/978-1-4615-0935-6}}
* {{Cite book| ref=harv|last=Sedgewick|first=Robert|last2=Wayne|first2=Kevin|authorlink=Robert Sedgewick (computer scientist)|title=Algorithms|year=2011|publisher=Addison-Wesley Professional|location=Upper Saddle River, NJ|isbn=978-0-321-57351-3|edition=4th|url=http://algs4.cs.princeton.edu/home/}}
* {{Cite book| ref=harv|last=Stroustrup|first=Bjarne|authorlink=Bjarne Stroustrup|title=The C++ Programming Language|edition=4th|year=2013|publisher=Addison-Wesley Professional|location=Upper Saddle River, NJ|isbn=978-0-321-56384-2}}
{{Литература крај}}
*

{{нормативна контрола}}

[[Категорија:Алгоритми претраживања]]