Binäre Suche mit Rekursion

In dieser Übung implementierst du den binären Suchalgorithmus, den du gerade gelernt hast, mithilfe von Rekursion. Erinnere dich daran, dass eine rekursive Funktion eine Funktion ist, die sich selbst aufruft.

Diese Übung ist Teil des Kurses

Datenstrukturen und Algorithmen in Python

Kurs anzeigen

Anleitung zur Übung

Definiere den Basisfall.
Überprüfe, ob der Suchwert mit dem Wert in der Mitte übereinstimmt.
Rufe die Funktion binary_search_recursive() rekursiv in der linken Hälfte der Liste auf.
Rufe die Funktion binary_search_recursive() rekursiv auf der rechten Hälfte der Liste auf.

Interaktive Übung

Versuche dich an dieser Übung, indem du diesen Beispielcode vervollständigst.

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))

Code bearbeiten und ausführen