Поделили смо колекцију ставки на две половине у Бинарној претрази да бисмо смањили број директних поређења потребних за откривање елемента. Међутим, постоји један захтев: ставке низа морају бити претходно сортиране.
Бинарно претраживање
Тхе Бинарно претраживање Метод лоцира индекс одређеног члана листе. То је један од најпопуларнијих и најбржих алгоритама. Да би процедура бинарног претраживања функционисала, уноси у листи треба да буду сортирани.
римски бројеви 1-100
Бинарно претраживање је ефикаснија техника претраживања за лоцирање индекса елемента од Линеар Сеарцх пошто не морамо да испитујемо сваки индекс листе.
Целокупна операција алгоритма бинарног претраживања може се сажети у следеће кораке:
- Пронађите средњи елемент у сортираном низу.
- Направите поређење између елемента који се налази и средњег елемента.
- Ако је тај елемент једнак средњем елементу дате листе, онда се враћа индекс средњег елемента. У супротном, алгоритам ће упоредити елемент са ставком у средини.
- Сада, ако је елемент који треба лоцирати већи од средње ставке листе, упоредиће се са десном половином листе, односно са елементима иза средњег индекса.
- Или ако је елемент мањи од елемента у средини листе, онда ће се упоредити само са левом половином листе, односно са елементима пре средњег индекса.
Рекурзивно бинарно претраживање
Бинарна претрага подразумева континуирано дељење интервала претраживања на 2 једнака дела да би се открио елемент у сортираном низу, а понављајућа бинарна претрага подразумева разбијање комплетне процедуре бинарног претраживања на мање проблеме. Рекурзивна бинарна претрага је рекурзивни одговор на бинарну претрагу.
Следе карактеристике које потпуно рекурзивна решења морају да испуњавају:
- Основни случај је неопходан за рекурзивни приступ.
- Мора постојати рекурзивни тест случај у рекурзивном приступу.
- Рекурзивни приступ мора да се приближи основном случају.
Најнижу подјелу компликованог проблема представља основни случај, који је коначни случај. Дакле, да би се извршила бинарна претрага рекурзивном методом, наш алгоритам мора да садржи основни случај и рекурзивни случај, при чему рекурзивни случај напредује до основног случаја. Иначе се процес никада не би завршио и резултирао бесконачном петљом.
Техника бинарног претраживања смањује време потребно да се пронађе одређени елемент унутар сортираног низа. Метода бинарне претраге се често имплементира итеративно, али можемо је применити и рекурзивно тако што ћемо је разбити на мање делове.
Код
деинсталирајте ангулар цли
#defining a function to execute Binary Search on any given sorted list L. #start is the lowest index of the list being checked at any given time. #end is the highest index of the list being checked at any given time. #item is the item to be searched in the list. def binary_search(L, start, end, item): if end >= start: middle = (start + end) // 2 if L[middle] == item: return middle #middle element is the item to be located #if middle item is greater than the item to be searched, left side of the list will be searched elif L[middle] > item: #starting index will be same but ending index will be the middle of the main list i.e. left half of the list is given in function. return binary_search(L, start, middle - 1, item) else: #if middle item is smaller than the item to be searched, new starting index will be middle of the list i.e. right half of the list. return binary_search(L, middle + 1, end, item) else: #if element is not present in the list return -1 #Drivers code my_list = [ 2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22 ] element_to_search = 6 print('The given list is') print(my_list) index_of_element = binary_search(my_list, 0, len(my_list)-1, element_to_search) if index_of_element != -1: print('Element searched is found at the index ', str(index_of_element), 'of given list') else: print('Element searched is not found in the given list!')
Излаз:
The given list is [2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22] Element searched is found at the index 2 of given list
Рекурзија је изузетно моћна техника програмирања и решавања проблема. Можемо га користити за процену и извршавање различитих алгоритама, у распону од једноставних итеративних проблема до компликованих проблема враћања назад. У овом водичу смо погледали коришћење језика Питхон за креирање рекурзивне методе бинарног претраживања.