再帰を使った二分探索
この演習では、今学んだ二分探索アルゴリズムを再帰を使って作成します。再帰関数とは、自分自身を呼び出す関数のことです。
この演習はコースの一部です
Pythonで学ぶデータ構造とアルゴリズム
演習の手順
- ベースケースを定義してください。
- 探索する値がリストの中央の値と等しいかどうかを確認してください。
binary_search_recursive()関数をリストの左半分に対して再帰的に呼び出してください。binary_search_recursive()関数をリストの右半分に対して再帰的に呼び出してください。
実践的なインタラクティブ演習
このサンプルコードを完成させて、この演習に挑戦してみましょう。
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))