파이썬 알고리즘 기초 - 재귀적 이진탐색 설명

문제 설명

리스트 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 을 리턴해야 합니다.

Python 동작 코드

def rec_bin_search(L, x, l, u):
    if l>u:
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return rec_bin_search(L, x, l, mid-1)
    else:
        return rec_bin_search(L, x, mid+1, u)

Q1. if 조건문에서 l>u가 아닌 x not in L 을 써도 상관 없지 않나?

A2. 결과값만 본다면 똑같은 결과가 나온다. 하지만 효율성이 떨어진다. 파이썬의 포함 연산자는 O(n)의 복잡도를 가진다. 이진탐색을 하는 이유가 복잡도를 O(n)에서 O(log n)으로 줄이기 위함인데, x not in L을 쓰는 것은 효율적이지 않은 방식이다.

Q2. 왜 재귀함수에서 rec_bin_search 부분에서 l 대신 mid가 아닌 mid+1, u 대신 mid가 아닌 mid-1이 들어갔을까?

A2. mid를 인덱스로 갖는 값 자체가 조건 연산에서 이미 작거나 크다고 나와있기 때문에 그 값보다 작다면 mid의 인덱스보다 한칸 크거나 작은 인덱스를 가지는 것이 무한 루프에 빠지지 않게 한다.

한줄한줄 따라가는 시뮬레이션

case1. 리스트 L안에 찾으려는 원소x가 존재하는 경우

L = [1, 3, 7, 9, 13, 14, 17, 21, 24, 27, 31] 이라 하고, 이때의 rec_bin_search(L, 17, 0, 10)을 실행을 시뮬레이션 해보자.

#Step1
def rec_bin_search(L, x, l, u):
    if l>u: 						# l=0, u=10, 0<10이므로 조건만족x
        return -1				
    mid = (l + u) // 2					# mid = (0 + 10)//2 => 5
    							# l=0, u=10, x=17, L[mid] = 14
    if x == L[mid]:					
        return mid
    elif x < L[mid]:
        return rec_bin_search(L, x, l, mid-1)
    else:							
        return rec_bin_search(L, x, mid+1, u)		# l=(mid+1)=6, u=10, x=17