[코드잇][알고리즘의 정석]토픽 2: 재귀 함수 연습-05. 이진 탐색 재귀로 구현해보기

[코드잇][알고리즘의 정석]토픽 2: 재귀 함수 연습-05. 이진 탐색 재귀로 구현해보기

 

링크: https://www.codeit.kr/learn/courses/algorithms/1133

코딩이 처음이라면, 코드잇

 

---

문제

이진 탐색 알고리즘을 이미 반복문으로는 구현해 보셨죠? 이번에는 재귀적으로 문제를 해결해 보세요.

반드시 재귀(recursion)의 개념을 사용하셔야 합니다. 코드 구현이 꽤 어려우니, 천천히 고민해 보시기 바랍니다. 다른 재귀 문제를 풀 때와 마찬가지로 base case와 recursive case를 생각해 내는 것이 핵심입니다!

 

 

def binary_search(element, some_list, start_index=0, end_index=None):
    # end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스
    if end_index == None:
        end_index = len(some_list) - 1

    # 코드를 작성하세요.

print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

 

0
None
2
1
4

---

제출한 답

def binary_search(element, some_list, start_index=0, end_index=None):
    # end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스
    if end_index == None:
        end_index = len(some_list) - 1

    # 코드를 작성하세요.
    if start_index > end_index: return None
        
    i = (start_index + end_index) //2
    
    if element == some_list[i]:
        return i
    elif element < some_list[i]:
        return binary_search(element, some_list, start_index, i-1)
    else:
        return binary_search(element, some_list, i+1, end_index)

print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))