W wyszukiwaniu binarnym podzieliliśmy zbiór elementów na dwie połowy, aby zmniejszyć liczbę bezpośrednich porównań potrzebnych do odkrycia elementu. Jest jednak jeden wymóg: elementy tablicy muszą zostać wcześniej posortowane.
Wyszukiwanie binarne
The Wyszukiwanie binarne Metoda lokalizuje indeks określonego elementu listy. Jest to jeden z najpopularniejszych i najszybszych algorytmów. Aby procedura Wyszukiwania Binarnego zadziałała należy posortować wpisy na liście.
dzielenie ciągu w c++
Wyszukiwanie binarne jest bardziej efektywną techniką wyszukiwania służącą do lokalizowania indeksu elementu niż Wyszukiwanie liniowe ponieważ nie musimy sprawdzać każdego indeksu listy.
Całe działanie algorytmu wyszukiwania binarnego można podsumować w następujących krokach:
- Znajdź środkowy element posortowanej tablicy.
- Dokonaj porównania pomiędzy lokalizowanym elementem i środkowym elementem.
- Jeżeli element ten jest równy środkowi danej listy, to zwracany jest indeks środkowego elementu. W przeciwnym razie algorytm porówna element z elementem znajdującym się pośrodku.
- Teraz, jeśli element, który ma zostać zlokalizowany, jest większy niż środkowy element listy, zostanie porównany z prawą połową listy, czyli elementami znajdującymi się po środkowym indeksie.
- Lub jeśli element jest mniejszy niż element na środku listy, wówczas zostanie porównany tylko z lewą połową listy, czyli elementami znajdującymi się przed środkowym indeksem.
Rekurencyjne wyszukiwanie binarne
Wyszukiwanie binarne oznacza ciągłe dzielenie interwału wyszukiwania na 2 równe części w celu wykrycia elementu w posortowanej tablicy, a powtarzalne wyszukiwanie binarne pociąga za sobą podzielenie całej procedury wyszukiwania binarnego na mniejsze elementy. Rekurencyjne wyszukiwanie binarne jest odpowiedzią rekurencyjną na wyszukiwanie binarne.
wewnętrzne działanie hashmap
Poniżej przedstawiono cechy, które muszą spełniać rozwiązania w pełni rekurencyjne:
- W przypadku podejścia rekurencyjnego wymagany jest przypadek podstawowy.
- W podejściu rekurencyjnym musi istnieć rekurencyjny przypadek testowy.
- Podejście rekurencyjne musi zbliżyć się do przypadku podstawowego.
Najniższy podział skomplikowanego problemu reprezentuje przypadek podstawowy, który jest przypadkiem końcowym. Zatem, aby przeprowadzić wyszukiwanie binarne metodą rekurencyjną, nasz algorytm musi zawierać przypadek podstawowy i przypadek rekurencyjny, przy czym przypadek rekurencyjny przechodzi do przypadku podstawowego. W przeciwnym razie proces nigdy by się nie zakończył i utworzyłby nieskończoną pętlę.
Technika wyszukiwania binarnego skraca czas potrzebny na znalezienie określonego elementu w posortowanej tablicy. Metoda wyszukiwania binarnego jest często implementowana iteracyjnie, ale możemy ją również wdrożyć rekurencyjnie, dzieląc ją na mniejsze części.
Kod
uri vs adres URL
#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!')
Wyjście:
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
Rekurencja jest niezwykle potężną techniką programowania i rozwiązywania problemów. Możemy go używać do oceny i wykonywania różnych algorytmów, od prostych problemów iteracyjnych po skomplikowane problemy z cofaniem się. W tym samouczku przyjrzeliśmy się używaniu języka Python do tworzenia rekursywnej metody wyszukiwania binarnego.