Tìm kiếm nhị phân bằng đệ quy
Trong bài tập này, bạn sẽ hiện thực thuật toán tìm kiếm nhị phân mà bạn vừa học bằng đệ quy. Nhớ rằng hàm đệ quy là hàm tự gọi chính nó.
Bài tập này là một phần của khóa học
Cấu trúc dữ liệu và Thuật toán với Python
Hướng dẫn bài tập
- Xác định trường hợp cơ sở.
- Kiểm tra xem giá trị cần tìm có bằng giá trị ở giữa hay không.
- Gọi lại hàm
binary_search_recursive()theo cách đệ quy trên nửa bên trái của danh sách. - Gọi lại hàm
binary_search_recursive()theo cách đệ quy trên nửa bên phải của danh sách.
Bài tập tương tác thực hành trực tiếp
Hãy thử làm bài tập này bằng cách hoàn thành đoạn mã mẫu này.
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))