Binaire zoekopdracht met recursie

In deze oefening implementeer je het algoritme binary search dat je zojuist hebt geleerd met recursie. Onthoud dat een recursieve functie een functie is die zichzelf aanroept.

Deze oefening maakt deel uit van de cursus

Datastructuren en algoritmen in Python

Cursus bekijken

Oefeninstructies

Definieer het basisgeval.
Controleer of de gezochte waarde gelijk is aan de waarde in het midden.
Roep de functie binary_search_recursive() recursief aan op de linkerhelft van de lijst.
Roep de functie binary_search_recursive() recursief aan op de rechterhelft van de lijst.

Praktische interactieve oefening

Probeer deze oefening eens door deze voorbeeldcode in te vullen.

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 bewerken en uitvoeren