Ние разделяме колекция от елементи на две половини в Binary Search, за да намалим броя на директните сравнения, необходими за откриване на елемент. Има обаче едно изискване: елементите на масива трябва да бъдат сортирани предварително.
Двоично търсене
The Двоично търсене Методът намира индекса на определен член на списъка. Той е сред най-популярните и бързи алгоритми. За да работи процедурата за двоично търсене, записите в списъка трябва да бъдат сортирани.
Двоично търсене е по-ефективна техника за търсене за намиране на индекс на елемент от Линейно търсене тъй като не е нужно да проверяваме всеки индекс на списък.
Цялата операция на алгоритъма за двоично търсене може да бъде обобщена в следните стъпки:
- Намерете средния елемент в сортирания масив.
- Направете сравнение между елемента, който трябва да бъде разположен, и средния елемент.
- Ако този елемент е равен на средния елемент от дадения списък, тогава се връща индексът на средния елемент. В противен случай алгоритъмът ще сравни елемента с елемента в средата.
- Сега, ако елементът, който трябва да се намери, е по-голям от средния елемент на списъка, той ще бъде сравнен с дясната половина на списъка, т.е. елементите след средния индекс.
- Или ако елементът е по-малък от елемента в средата на списъка, тогава той ще бъде сравнен само с лявата половина на списъка, т.е. елементите преди средния индекс.
Рекурсивно двоично търсене
Двоичното търсене предполага непрекъснато разделяне на интервала на търсене на 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
Рекурсията е изключително мощна техника за програмиране и решаване на проблеми. Можем да го използваме, за да оценим и изпълним различни алгоритми, вариращи от прости итеративни проблеми до сложни проблеми с обратно проследяване. В този урок разгледахме използването на езика Python за създаване на метода за рекурсивно двоично търсене.