[파이썬 기초] 알고리즘의 개념 / 코딩 연습 - 예제8(재귀함수 연습 - 이진 탐색 알고리즘)

# 재귀 함수(recursive function)  : 자기 자신을 호출하는 함수

   (improvemyself.tistory.com/82?category=849184)

[파이썬 기초] 알고리즘의 개념 / 코딩 연습 - 재귀함수의 개념(카운트다운 함수, 팩토리얼 함수)

# 이전 글 중 반복문을 사용하여 이진 탐색 알고리즘을 만들어 보았는데, 

   (improvemyself.tistory.com/80)

[파이썬 기초] 알고리즘의 개념 / 코딩 연습 - 예제3(이진 탐색 알고리즘)

  이번에는 반복문이 아닌 재귀함수를 사용하여 이진 탐색 알고리즘을 만드는 것이 과제이다.

 

코드잇 예제풀이(재귀함수 문제) : 파라미터로 탐색할 값 element와 리스트 some_list를 받고, 그 위치(인덱스) 혹은 None를 리턴하는 재귀함수 binary_search를 작성(조건 : 반복문 사용하지 말것)

 

 

Hint 1 : 재귀함수의 recursive case와 base case를 구분 : 여기서 base case는 1) 즉시 None이 리턴되는 경우 2) 즉시 element의 인덱스가 리턴되는 경우의 2가지이다. 

 

1)의 경우는 some_list 안에 element가 없다는 것을 확신할 수 있는 경우인데, 이 경우는 탐색 범위의 크기가 1인데도 some_list에서 element를 찾지 못하는 경우이다. 이렇게 되면 다시 탐색 범위를 줄이게 되어 start_index와 end_index가 교차하여 start_index가 end_index보다 커지게 된다. → 이 경우 None을 리턴

 

2)의 경우는 첫 시도에 some_list안에서 element를 바로 찾는 경우이다. 기존에 이진 탐색 알고리즘에서 작성했던 것과 마찬가지로 midpoint를 활용하면 된다. → 이 경우 midpoint를 리턴

 

Hint 2 : recursive case는 나머지 경우(바로 판단이 불가능한 경우)인데, 1) element가 midpoint보다 크면 오른쪽 반을 탐색, 2) element가 midpoint보다 작으면 왼쪽 반을 탐색하면 된다. 기존에 이진 탐색 알고리즘에서 작성했던 것을 활용하여 작성해보자.

 

============================================================

 

def binary_search(element, some_list, start_index = 0, end_index = None): 

     # end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스

     if end_index == None :

         end_index = len(some_list) - 1

 

     # base case (1)

     if start_index > end_index :

         return None

 

     midpoint = (start_index + end_index) // 2

 

     # base case (2)

     if some_list[midpoint] == element :

         return midpoint

 

     # element가 midpoint보다 작은 경우(왼쪽 반을 탐색)

     elif some_list[midpoint] > element :

         return binary_search(element, some_list, start_index, midpoint - 1)

 

     # element가 midpoint보다 큰 경우(오른쪽 반을 탐색)

     else :

           return binary_search(element, some_list, midpoint + 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]))

 

0

None

2

1

4