Бинарна претрага

Бинарна претрага

Бинарно петраживачки низ
Класа	Алгоритам сортирања
Структура података	Низ
Најгора перформанца	$O(logn)$
Најбоља перформанца	$O(logn)$
Најгора просторна комплексност	$O(n)$

У рачунарству, бинарна претрага или претрага методом половљених интервала је алгоритам проналажења индекса одређеног елемента - кључа у сортираном низу. У сваком кораку, алгоритам упоређује вредност кључа (вредност коју се тражи) са вредношћу средишњег члана низа. Уколико се вредности подударају, алгоритам се завршава, у супротном, уколико је вредност кључа мања од вредности средишњег члана алгоритам се понавља на леви подниз у односу на средишњи елемент. Ако је кључ већи од средишњег члана онда се алгоритам примењује на десни подниз. Овај процес се понавља све док кључ није нађен, или док подниз не постане празан, што значи да се кључ не налази у низу.

Бинарна претрага у најгорем случају поседује логаритамску временску сложеност, радећи $O(\log n)$ поређења где је $n$ број елемената у низу.

Алгоритам

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

Процедура

За дати низ $A$ који се састоји од $n$ елемената са вредностима $A_{0},A_{1},A_{2},\ldots ,A_{n-1}$ сортирани тако да $A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}$ и тражену вредност $T$, следећа подрутина користи бинарну претрагу да нађе индекс $T$ у низу $A$

1. Поставити да је $L$ једанако $0$ и да је $R$ једнако $n-1$.
2. Ако је $L>R$, претрага се зауставља као неуспешна.
3. Поставити $m$ (позицију средњег елемента) да буде једнако floor функцији вредности ${\frac {L+R}{2}}$.
4. Ако је $A_{m}<T$, поставити $L$ да буде једнако $m+1$ па отићи на корак 2.
5. Ако је $A_{m}>T$, поставити $R$ да буде једнако $m-1$ па отићи на корак 2.
6. $A_{m}=T$ претрага је готова и враћа се $m$.

Ова итеративна процедура прати границе претраге са две променљиве $L$ и $R$. Процедура може бити представљена у следећем псеудокоду, у ком су промељиве именоване као у пре напоменутој процедури, где neuspeh представља вредност која означава неуспех претраге.

Бинарна претрага

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

Перформансе

У сваком тесту који не успе да пронађе тражени кључ, претрага се наставља у једном или другом подинтервалу који је дупло мањи по величини од полазног. Тачније, уколико је величина показног интевала N , тада подинтевали садрже по N/2 или N/2-1 елемената.

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

Литература

• Томашевић, Мило (2008). „1”. Алгоритми и структуре података (1st изд.). Београд: Академска мисао. стр. 406. ISBN 978-86-7466-328--8. Приступљено 09. 02. 2016. „Сложеност алгоритама” 
• Шкарић, Милан; Виктор, Радовић (2009). „5”. Увод у програмирање (прво изд.). Београд: Микро књига. стр. 205. ISBN 978-86-7555-349-6. Приступљено 09. 02. 2016. „Претрага низа” 
• Introductions to algorithms -Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein, књигу можете погледати овде Архивирано на сајту Wayback Machine (18. октобар 2016)
• Алгоритми и структуре података - Мило Томашевић
• Увод у програмирање - Милан Шкарић
• 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 изд.). 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 изд.). 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 изд.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-57351-3. 
• Stroustrup, Bjarne (2013). The C++ Programming Language (4th изд.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-56384-2.