[알고리즘] 이진 탐색(Binary Search)

이진 탐색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 

 

처음에 중간의 값을 임의의 값으로 선택하여 그 값과 찾고자 하는 값의 크고 작음을 비교하여 찾고자 하는 값을 찾아간다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 

 

 

이제 이진 탐색 맛보기를 해보자!

 

단어가 아주 많이 있는 영어사전에서 Program 이라는 단어를 찾는다고 가정해보자. 

단, P 로 시작하는 단어의 첫 페이지로 가지 않고, 사전을 펼치는 작업을 반복해서 찾아보자. 물론, 펼치는 횟수가 적을 수록 좋다.

 

어떤 페이지를 펼치는 것이 좋을까?

가장 좋은 방법은 전체 페이지의 반이 되는 페이지를 펼쳐서 Program 이라는 단어가 있는지 살펴보는 것이다. 

그리고 페이지에 어떤 알파벳으로 시작하는 단어가 있는지 살펴보는 것이다. 

 

P 이전의 알파벳이 적혀있다면 P 로 시작하는 Program 을 찾기 위해서는 반~끝 페이지까지를 뒤져야하고,

P 이후의 알파벳이 적혀있다면 P 로 시작하는 Program 을 찾기 위해서는 처음~반 페이지까지를 뒤져야한다. 

 

계속해서 찾는 범위의 반이 되는 페이지를 펼치면서 찾아가면, 나중에는 1장만 남게 될 것이다. 

 

이렇게 찾는 범위를 반씩 줄여가면서 원하는 값을 찾는 것이 이진 탐색이다. 

 

 

그럼 이제 이진 탐색 코드를 살펴보자.

 

- Slicing 을 이용한 재귀적으로 이진 탐색하기

def binary_search(A, K): 
    if len(A) < 1: # 존재하지 않으면 -1 리턴
        return -1
    m = len(A) // 2 # 범위의 반
    if A[m] < K:
        return binary_search(A[m+1:], K)
    eljf A[m] > K:
        return binary_search(A[:m], K) 
    else:
        return m # 존재하면 인덱스 리턴

 

수행 시간 T(n) 을 계산해보면, T(n) = 1 + n + T(n/2)

• 비교하는 시간: 1
• slicing 복사시간: n
• 줄어든 범위에서 재귀탐색: T(n/2)

점화식을 끝까지 계산하면, 시간 복잡도는 O(n) 이 된다. 

 

T(n) = 1 + n + T(n/2)

        = 1 + n + (1 + n/2 + T(n/4))

        = . . .

        = C + Cn(1 + 1/2 + 1/4 + ... )

        = C + 2Cn  ( 1 + 1/2 + 1/4 + ... -> 2에 매우 근접하지만 절대 2가 될 수 없음, 아무튼 대충 2로 계산함!)

 

이 코드는 재귀와 슬라이싱 연산을 이용하기 때문에 시간이 많이 걸린다. 

특히 슬라이싱 연산은 리스트의 일부분을 복사하기 때문에 수행시간이 늘어나는 부작용이 있다. 

 

 

이제 Slicing 을 이용하지 않고 재귀를 사용한 코드를 살펴보자. 

 

- Slicing 을 이용하지 않고 재귀적으로 이진 탐색하기

def binary_search(A, left, right, K):
    if left > right: # 존재하지 않으면 -1 리턴
        return -1
    m = (left + right) // 2 # 범위의 반
    if A[m] > K:
        return binary_search(A, left, m-1, K)
    elif A[m] < K:
        return binary_search(A, m+1, right, K)
    else:
        return m # 존재하면 인덱스 리턴

 

수행 시간 T(n) 을 계산해보면, T(n) = 1 + T(n/2)

• 비교하는 시간: 1
• 줄어든 범위에서 재귀탐색: T(n/2)

점화식을 끝까지 계산하면, 시간 복잡도는 O(log2 n)

 

 

- Slicing 을 이용하지 않고 비재귀적으로 이진 탐색하기

def binary_search(A, K):
    left, right = 0, len(A) # 범위의 처음, 끝
    while left - right >= 0:
        m = (left + right) // 2 # 범위의 중간
        if A[m] > K: 
            right = m - 1
        elif A[m] < K:
            left = m + 1
        else:
            return m

 

수행 시간 T(n) 을 계산해보면, T(n) = 1 + T(n/2)

• 비교하는 시간: 1
• 줄어든 범위에서 재귀탐색: T(n/2)

점화식을 끝까지 계산하면, 시간 복잡도는 O(log2 n) (계산 과정은 위와 똑같으니 생략함)

 

그러나 재귀를 사용하지 않은 이번 코드가 더 바람직한 이진 탐색 코드!

-> 재귀를 사용하면 큰 입력에 대해 스택 오버플로우 위험이 있고, 추가적인 메모리 사용이 있기 때문!

 

 

대표적인 이진 탐색 문제 몇가지

 

- 나무 자르기
https://www.acmicpc.net/problem/2805

 

- 예산

https://www.acmicpc.net/problem/2512

 

- 랜선 자르기

https://www.acmicpc.net/problem/1654

 

 

참고 자료

- 신찬수 교수님 알고리즘 강의 자료

- 나무위키