使用遞迴的 Binary search

在這個練習中，你要用遞迴來實作你剛學到的Binary search 演算法。回想一下，遞迴函式是指會呼叫自己的函式。

本練習屬於課程

Data Structures and Algorithms in Python

練習說明

定義基底情況（base case）。
檢查欲搜尋的值是否等於中間位置的值。
對串列左半部遞迴呼叫 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))

編輯並執行程式碼