related post : 백준에서 재귀함수 풀기

어서와! 자료구조와 알고리즘은 처음이지? 5강 : 재귀 알고리즘 응용


재귀함수란?

하나의 함수에서 자신을 다시 호출해서 문제를 해결하는 방법 


재귀적 알고리즘은 사람의 논리와 비슷해 직관적이지만, 카운터 파트인 반복적인 방법에 비해서 효율성이 떨어진다는 단점을 갖는다. 효율성 단점에도 불구하고 재귀 알고리즘은 여전히 유용하다. 


문제 

리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어지고, 또한 탐색의 대상이 되는 리스트 내에서의 범위 인덱스가 l 부터 u 까지로 (인자로) 정해질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.
인덱스 범위를 나타내는 l 과 u 가 인자로 주어지는 이유는, 이 함수를 재귀적인 방법으로 구현하기 위함입니다. 빈 칸에 알맞은 내용을 채워서 재귀 함수인 solution() 을 완성하세요.
예를 들어,
L = [2, 3, 5, 6, 9, 11, 15]
x = 6
l = 0
u = 6
의 인자들이 주어지면, L[3] == 6 이므로 3 을 리턴해야 합니다.
또 다른 예로,
L = [2, 5, 7, 9, 11]
x = 4
l = 0
u = 4
로 주어지면, 리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴해야 합니다.
이 연습문제에서는 알고리즘의 효율성도 평가합니다. 만약 순차 (선형) 탐색 알고리즘을 구현하는 경우에는 제한 시간 요구사항을 만족하지 못하여 효율성 테스트 케이스들을 통과하지 못할 수도 있습니다.

정답 코드는 다음과 같다. 



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def binsearch(L, x, lower, upper):
    if u-l == 1:
        return -1
    mid = (lower + upper) // 2
    
    if x == L[mid]:
        return mid
    
    elif x < L[mid]:
        return binsearch(L, x, l, mid)
    else:
        return binsearch(L, x, mid, u)