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

(преусмерено са Binarno pretraživanje)

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

Бинарна претрага
Бинарно петраживачки низ
КласаАлгоритам сортирања[1]
Структура податакаНиз[1]
Најгора перформанца[2]
Најбоља перформанца[2]
Најгора просторна комплексност[2]

Бинарна претрага у најгорем случају поседује логаритамску временску сложеност, радећи поређења где је број елемената у низу.[3]

Алгоритам

уреди

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

Процедура

За дати низ   који се састоји од   елемената са вредностима   сортирани тако да   и тражену вредност  , следећа подрутина користи бинарну претрагу да нађе индекс   у низу  [4]

  1. Поставити да је   једанако   и да је   једнако  .
  2. Ако је  , претрага се зауставља као неуспешна.
  3. Поставити   (позицију средњег елемента) да буде једнако floor функцији[а] вредности  .
  4. Ако је  , поставити   да буде једнако   па отићи на корак 2.
  5. Ако је  , поставити   да буде једнако   па отићи на корак 2.
  6.   претрага је готова и враћа се  .

Ова итеративна процедура прати границе претраге са две променљиве   и  . Процедура може бити представљена у следећем псеудокоду, у ком су промељиве именоване као у пре напоменутој процедури, где 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 итерација. Примећујемо да је бинарна претрага знатно бржа од линеарне. На пример, уколико претражујемо низ од милион чланова, у линеарној претрази бисмо имали исто толико корака, а у бинарној претрази никад више од двадесет итерација. Мана бинарне претраге је у томе што се овим алгоритмом не може претражити низ који није сотриран.

Напомене

уреди
  1. ^ Функција која заокружује дати број на први цео број који је мањи или једнак датом броју (нпр. за 2.6 излаз би био 2)

Референце

уреди
  1. ^ а б Шкарић 2009, стр. 205
  2. ^ а б в Томашевић 2008, стр. 406
  3. ^ Flores, Ivan; Madpis, George (1. 9. 1971). „Average binary search length for dense ordered lists”. Communications of the ACM. 14 (9): 602—603. ISSN 0001-0782. S2CID 43325465. doi:10.1145/362663.362752 . 
  4. ^ Knuth 1998, §6.2.1 ("Searching an ordered table"), субсекција "History and bibliography".

Литература

уреди