Објашњени алгоритми линеарног и бинарног претраживања

Способност претраживања неких података важан је аспект рачунарства. Алгоритми претраживања се користе за тражење одређене ставке у скупу података.

Алгоритми враћају логички резултат (тачан или нетачан) у упит за претрагу. Такође се могу модификовати тако да дају релативни положај пронађене вредности.

За овај чланак, алгоритми ће се концентрисати на утврђивање да ли вредност постоји.

Алгоритми линеарног претраживања

Линеарно претраживање познато је и као секвенцијално претраживање. У овој врсти претраживања, свака вредност на листи се посећује једна по једна на уредан начин, док се проверава да ли постоји жељена вредност.

Алгоритам проверава вредност по вредност док не пронађе вредност коју тражите или нема довољно вредности за претрагу. Када понестане вредности за претраживање, то значи да ваш упит за претрагу не постоји на листи.

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

Погледајте пример имплементације Питхона испод:

деф линеарСеарцх (моја листа, ставка):

пронађено = Нетачно

индекс = 0

док индек

иф милист [индек] == итем:

пронађено = Тачно

друго:

индекс = индекс+1

повратак пронађен

Алгоритамска анализа

Најбољи сценарио се дешава када је жељена ставка прва на листи. Најгори случај се дешава када је жељена ставка последња на листи (н -та ставка). Стога је временска сложеност линеарног претраживања О (н).

Просечан сценарио у горњем алгоритму је н/2.

Повезан: Шта је Биг-О нотација?

Измењена линеарна претрага

Важно је знати да коришћени алгоритам претпоставља да му је достављена насумична листа ставки. То јест, ставке листе нису у одређеном редоследу.

Претпоставимо да су ставке биле у одређеном редоследу, рецимо од најмањих до највећих. Било би могуће постићи неку предност у рачунању.

Узмите пример тражења 19 на датој листи: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Након 23 године постало би јасно да ставка коју тражите не постоји на листи. Због тога више не би било важно наставити претрагу по осталим ставкама листе.

Бинарни алгоритми претраживања

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

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

Ако је мање, нема потребе да проверавате доњу половину листе. У супротном, ако је већи, прелази се на горњу половину листе.

Повезан: Шта је рекурзија и како је користите?

Без обзира који подлист (леви или десни) изабран, средња вредност ће се поново одредити. Вредност се поново проверава да ли је потребна вредност. Ако није, проверава се да ли је мања или већа од захтеване вредности.

Овај процес се понавља све док се не пронађе вредност ако постоји.

Питхон имплементација испод служи за бинарни алгоритам претраживања.

деф бинариСеарцх (моја листа, ставка):

ниско = 0

хигх = лен (милист) - 1

пронађено = Нетачно

док је ниско <= високо и није пронађено:

мид = (ниско + високо) // 2

иф милист [мид] == итем:

пронађено = Тачно

елиф итем

висока = средина - 1

друго:

ниска = средња + 1

повратак пронађен

Алгоритамска анализа

Најбољи сценарио се дешава када се утврди да је жељена ставка средња ставка. Најгори могући сценарио ипак није тако једноставан. Пратите доњу анализу:

Након првог поређења, остаће н/2 ставки. Након друге, н/4 ставке ће бити остављене. После трећег, н/8.

Уочите да се број ставки наставља преполовљавати све док не досегну н/2и, гдје је и број поређења. Након цепања, завршавамо са само 1 ставком.

То подразумева:

н/2и = 1

Према томе, бинарна претрага је О (лог н).

Прелазимо на сортирање

У бинарном претраживању размотрили смо случај где је дати низ већ наручен. Али претпоставимо да имате неуређен скуп података и да желите да извршите бинарно претраживање по њему. Шта би ти урадио?

Одговор је једноставан: средите га. Постоје бројне технике сортирања у рачунарству које су добро истражене. Једна од ових техника коју можете почети проучавати је алгоритам сортирања избора, док имамо доста водича везаних и за друга подручја.

Како се користи сортирање избора

За почетнике је мало тешко разумјети одабир, али то није превише изазовно када схватите ствари.

Прочитајте следеће

О аутору