Пре него што научимо бинарну претрагу, научимо:
Шта је претрага?
Претрага је услужни програм који омогућава свом кориснику да пронађе документе, датотеке, медије или било коју другу врсту података која се налази у бази података. Претрага ради на једноставном принципу подударања критеријума са записима и приказивања кориснику. На тај начин функционише најосновнија функција претраживања.
Шта је бинарна претрага?
Бинарно претраживање је напредни тип алгоритма претраживања који проналази и преузима податке са сортиране листе ставки. Његов основни принцип рада укључује поделу података на листи на пола док се тражена вредност не пронађе и не прикаже кориснику у резултату претраге. Бинарна претрага је обично позната као претрага са пола интервала или логаритамска претрага .
У овом упутству за алгоритам научићете:
- Шта је претрага?
- Шта је бинарна претрага?
- Како функционише бинарна претрага?
- Пример бинарне претраге
- Зашто нам је потребна бинарна претрага?
Како функционише бинарна претрага?
Бинарна претрага ради на следећи начин:
- Процес претраживања започиње лоцирањем средњег елемента разврстаног низа података
- Након тога, кључна вредност се упоређује са елементом
- Ако је вредност кључа мања од средњег елемента, претрага анализира горње вредности средњег елемента ради поређења и подударања
- У случају да је вредност кључа већа од средњег елемента, претрага анализира ниже вредности средњег елемента ради поређења и подударања
Пример бинарне претраге
Погледајмо пример речника. Ако требате да пронађете одређену реч, нико не пролази кроз сваку реч узастопно, већ насумично проналази најближе речи да би тражио потребну реч.
Горња слика илуструје следеће:
- Имате низ од 10 цифара и потребно је пронаћи елемент 59.
- Сви елементи су означени индексом од 0 - 9. Сада се израчунава средина низа. Да бисте то урадили, узимате крајњу леву и десну вредност индекса и делите их са 2. Резултат је 4,5, али ми узимамо најнижу вредност. Отуда је средина 4.
- Алгоритам спушта све елементе са средње (4) на најнижу границу, јер је 59 веће од 24, а сада је у низу остало само 5 елемената.
- Сада је 59 веће од 45, а мање од 63. Средње је 7. Отуда десна вредност индекса постаје средња - 1, што је једнако 6, а лева вредност индекса остаје иста као и раније, што је 5.
- У овом тренутку знате да 59 долази после 45. Дакле, леви индекс, који је 5, такође постаје средњи.
- Те се итерације настављају све док се низ не смањи на само један елемент или док ставка коју треба пронаћи постане средина низа.
Пример 2
Погледајмо следећи пример да бисмо разумели како функционише бинарна претрага
- Имате низ сортираних вредности у распону од 2 до 20 и треба да пронађете 18.
- Просек доње и горње границе је (л + р) / 2 = 4. Тражена вредност је већа од средине која износи 4.
- Вредности низа мање од средине избацују се из претраге и претражују се вредности веће од средње вредности 4.
- Ово је понављајући поступак дељења док се не пронађе стварна ставка коју треба претражити.
Зашто нам је потребна бинарна претрага?
Следећи разлози чине бинарно претраживање бољим избором који ће се користити као алгоритам претраживања:
- Бинарна претрага ефикасно ради на сортираним подацима без обзира на величину података
- Уместо да врши претрагу пролазећи кроз податке у низу, бинарни алгоритам насумично приступа подацима како би пронашао потребан елемент. То чини циклусе претраживања краћим и тачнијим.
- Бинарна претрага врши поређење сортираних података на основу принципа редоследа него упоређивање једнакости, које су спорије и углавном нетачне.
- После сваког циклуса претраживања, алгоритам дели величину низа на половину, па ће у следећој итерацији радити само на преосталој половини низа
Резиме
- Претрага је услужни програм који омогућава свом кориснику да претражује документе, датотеке и друге врсте података. Бинарно претраживање је напредни тип алгоритма претраживања који проналази и преузима податке са сортиране листе ставки.
- Бинарна претрага је обично позната као претрага са пола интервала или логаритамска претрага
- Функционише тако што се низ подели на пола на свакој итерацији испод траженог елемента.
- Бинарни алгоритам узима средину низа тако што зброј вредности левог и десног индекса дели са 2. Сада алгоритам спушта или доњу или горњу границу елемената са средине низа, у зависности од елемента који треба пронаћи .
- Алгоритам насумично приступа подацима како би пронашао потребан елемент. То чини циклусе претраживања краћим и тачнијим.
- Бинарна претрага врши упоређивање сортираних података на основу принципа редоследа него коришћење поређења једнакости које су споро и нетачно.
- Бинарна претрага није погодна за неразврстане податке.