재귀를 사용한 이진 탐색
이 연습 문제에서는 방금 배운 이진 탐색 알고리즘을 재귀로 구현해 보겠습니다. 재귀 함수는 자기 자신을 호출하는 함수라는 점을 기억하세요.
이 연습은 강의의 일부입니다
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))