Wyszukiwanie binarne z użyciem rekurencji
W tym ćwiczeniu zaimplementujesz algorytm wyszukiwania binarnego, którego właśnie się nauczyłeś, używając rekurencji. Przypomnij sobie, że funkcja rekurencyjna to funkcja, która wywołuje samą siebie.
To ćwiczenie jest częścią kursu
Struktury danych i algorytmy w Pythonie
Instrukcje do ćwiczenia
- Zdefiniuj przypadek bazowy.
- Sprawdź, czy szukana wartość jest równa wartości znajdującej się w środku listy.
- Wywołaj funkcję
binary_search_recursive()rekurencyjnie na lewej połowie listy. - Wywołaj funkcję
binary_search_recursive()rekurencyjnie na prawej połowie listy.
Interaktywne ćwiczenie praktyczne
Spróbuj tego ćwiczenia, uzupełniając ten przykładowy kod.
def binary_search_recursive(ordered_list, search_value):
# Define the base case
if ____(ordered_list) == 0:
return False
else:
middle = len(ordered_list)//2
# Check whether the search value equals the value in the middle
if search_value == ____:
return True
elif search_value < ordered_list[middle]:
# Call recursively with the left half of the list
return ____(ordered_list[:middle], search_value)
else:
# Call recursively with the right half of the list
return ____
print(binary_search_recursive([1,5,8,9,15,20,70,72], 5))