Преглед садржаја:
Дефиниција - Шта значи бинарна претрага?
Алгоритам бинарног претраживања користи се за проналажење одређене вриједности садржане у сортираном низу. Радећи са принципом поделе и освајања, овај алгоритам претраживања може бити прилично брз, али упозорење је да подаци морају бити у сортираном облику. То функционише тако што започиње претрагу у средини низа и ради на спуштању прве доње или горње половине секвенце. Ако је средња вредност нижа од циљане вредности, то значи да претрага мора ићи вишу, ако не, тада треба гледати на силазни део матрице.
Бинарна претрага је позната и као полу-интервална претрага или логаритамска претрага.
Техопедија објашњава бинарну претрагу
Бинарна претрага је брз и ефикасан начин проналажења одређене циљне вредности из скупа наручених ставки. Покретањем на средини сортиране листе, може ефикасно смањити простор за претрагу на пола одређивањем да ли ће се уздићи или спустити на основу средње вредности у односу на циљану вредност.
На примјер, са циљаном вриједношћу 8 и простором за претраживање од 1 до 11:
- Пронађена је средња / средња вредност и тамо је постављен показивач, који је у овом случају 6.
- Циљ 8 је упоређен са 6. Будући да је 6 мање од 8, циљ мора бити у вишој половини.
- Показивач се премешта на следећу вредност (7) и упоређује са циљем. Мање је, па се показивач прелази на следећу већу вредност.
- Показивач је сада на 8. Ако упоредите ово са циљем, тачно је подударање, па је циљ пронађен.
Користећи бинарну претрагу, циљ је морао да се упореди само са три вредности. У поређењу са линеарном претрагом, почео би од прве вредности и померао се према горе, тражећи упоређивање циља са осам вредности. Бинарна претрага је могућа само уз наручени скуп података; ако су подаци насумично распоређени, линеарна претрага би дала резултате цијело вријеме, док би се бинарна претрага вјероватно заглавила у бесконачној петљи.
