![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/8/83/Binary_Search_Depiction.svg/langsr-640px-Binary_Search_Depiction.svg.png&w=640&q=50)
Бинарна претрага
From Wikipedia, the free encyclopedia
У рачунарству, бинарна претрага или претрага методом половљених интервала је алгоритам проналажења индекса одређеног елемента - кључа у сортираном низу. У сваком кораку, алгоритам упоређује вредност кључа (вредност коју се тражи) са вредношћу средишњег члана низа. Уколико се вредности подударају, алгоритам се завршава, у супротном, уколико је вредност кључа мања од вредности средишњег члана алгоритам се понавља на леви подниз у односу на средишњи елемент. Ако је кључ већи од средишњег члана онда се алгоритам примењује на десни подниз. Овај процес се понавља све док кључ није нађен, или док подниз не постане празан, што значи да се кључ не налази у низу.
![]() Бинарно петраживачки низ | |
Класа | Алгоритам сортирања[1] |
---|---|
Структура података | Низ[1] |
Најгора перформанца | |
Најбоља перформанца | |
Најгора просторна комплексност |
Бинарна претрага у најгорем случају поседује логаритамску временску сложеност, радећи поређења где је
број елемената у низу.[3]