Binärsökning med rekursion

I den här övningen ska du implementera binärsökningsalgoritmen du just lärt dig, med hjälp av rekursion. Kom ihåg att en rekursiv funktion är en funktion som anropar sig själv.

Den här övningen är en del av kursen

Datastrukturer och algoritmer i Python

Visa kurs

Övningsinstruktioner

Definiera basfallet.
Kontrollera om sökvärdet är lika med värdet i mitten.
Anropa funktionen binary_search_recursive() rekursivt på den vänstra halvan av listan.
Anropa funktionen binary_search_recursive() rekursivt på den högra halvan av listan.

Interaktiv övning med praktiskt arbete

Testa den här övningen genom att slutföra den här exempelkoden.

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

Redigera och kör kod