이분 탐색(Binary Search) + 매개 변수 탐색, 삼분 탐색 (Python)

이분 탐색(Binary Search)

이분 탐색이란 정렬된 배열에서 범위를 반씩 줄여나가면서 원하는 값을 탐색하는 방법으로, 분할 정복(Divide and Conquer)을 사용하는 대표적인 알고리즘 중 하나이다.

이분 탐색이라는 단어를 모르더라도, 업-다운 게임을 해봤다면 한 번쯤 써본적이 있는 기법일 것이다.

 

 

위 그림은 파란색 표시된 값 9를 이분 탐색으로 찾는 과정이다.

각 상황에서의 중앙값과 찾고자 하는 값을 비교하며 범위를 줄여나간다.

 

구현해보기(코드)

두 변수 $low$와 $high$를 이용해 탐색 범위를 관리할 것이다.

초기 범위를 0 ~ (배열의 길이 - 1)로 두고 범위를 점점 좁혀나가면 된다.

def binarySearch(arr, target):
    low, high = 0, len(arr) - 1
 
    # low가 high보다 크면 종료
    while low <= high:
        mid = (low + high) // 2 # 중앙값의 Index 계산
 
        # 1. 원하는 값을 찾으면 인덱스 반환
        if arr[mid] == target:
            return mid
 
        # 2. 원하는 값이 중앙값보다 작은 경우 우측 범위 축소
        if target < arr[mid]:
            high = mid - 1
        # 3. 원하는 값이 중앙값보다 큰 경우 좌측 범위 축소
        if target > arr[mid]:
            low = mid + 1
    
    return None # 못찾은 경우 None 출력

 

arr이 오름차순으로 정렬되었을 때에 적용되는 이분 탐색 코드이다.

이분 탐색은 기본적으로 반씩 줄여나가는 과정을 반복하므로 $O(Nlog_2N)$의 시간 복잡도를 가진다.

 

Lower Bound와 Upper Bound

위 코드에는 크게 두 가지의 문제점이 있다.

1. 찾고자 하는 값이 여러 개인 경우, 어떤 Index가 리턴되었는지 알 수 없다.
2. 찾고자 하는 값이 없는 경우, 이분 탐색 결과는 버려진다.

 

코드를 조금 바꿔서 위의 경우에도 의미 있는 값을 구해보자.

Lower Bound는 찾고자 하는 값 이상의 값이 처음 나오는 인덱스를 의미하며,
Upper Bound는 찾고자 하는 값을 초과하는 값이 처음 나오는 인덱스를 의미한다.

이 두 값들은 찾는 값의 개수와 관계 없이 항상 존재한다.

 

 

두 값을 구하는 방법은 딱 부등호 하나 차이밖에 없다.

def lower_bound(arr, target):
    low, high = 0, len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return low

def upper_bound(arr, target):
    low, high = 0, len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] <= target:
            low = mid + 1
        else:
            high = mid - 1

    return low

 

bisect 라이브러리

사실 파이썬에는 이분 탐색을 지원하는 라이브러리인 bisect가 존재하기 때문에, 코드를 일일이 짤 필요가 없다.

Lower Bound와 Upper Bound는 각각 bisect_left와 bisect_right 함수로 구할 수 있다.

import bisect

# arr에서 target의 Lower Bound 구하기
bisect.bisect_left(arr, target)

# arr에서 target의 Upper Bound 구하기
bisect.bisect_right(arr, target)

 

라이브러리를 사용하더라도 arr는 미리 정렬된 상태여야 함에 유의하자.

bisect 라이브러리는 위 기능 외에도 탐색 범위 지정, 해당 위치에 요소 추가 등을 지원하니 궁금하다면 공식 문서를 참고해보자.

 

매개 변수 탐색(Parametric Search)

지금까지의 이분 탐색이 배열 안의 값을 찾는 과정이었다면, 매개 변수 탐색은 배열 내에서 조건을 만족하는 값을 찾는 과정이다.

즉, 배열 내의 대소관계로 범위를 줄여나가는 것이 아니라 조건을 직접 설정하여 범위를 줄여나가는 방법이다.

 

매개 변수 탐색은 주로 최적화 문제를 결정 문제로 바꾸는 기법과 함께 사용된다.

예를 들어, "~~를 만족하는 K의 최솟값은 얼마인가?"라는 질문을 "K=?일 때, ~~를 만족하는 가?"로 바꾸는 것이다.

 

매개 변수 탐색은 개념 자체가 어렵다기보다는 조건을 만족하는지 여부를 확인하는 부분이 어려운 경우가 많다.

위 설명만으로는 잘 모르겠다면, 백준 2805번을 한 번 풀어보면 느낌이 올 것이다.

 

삼분 탐색(Tenary Search)

삼분 탐색은 매개변수 탐색의 일종으로, 볼록 함수의 최대/최소값을 찾을 때 사용한다.

 

이분 탐색은 정렬되어있는 단조 증가(혹은 감소) 수열에서 원하는 값을 찾는 데 쓰인다.

따라서 함수의 모양이 이차 함수처럼 봉우리가 존재하는 경우 이분 탐색만으로 원하는 값을 찾아낼 수 없다.

 

따라서 이 경우 기존의 이분 탐색을 변형, 구간을 2개가 아닌 3개로 나누어 범위를 어느 쪽으로 줄여야 할 지 판별한다.

 

예를 들어, 아래로 볼록한 그래프에서 최솟값을 찾는다고 가정해보자.

$low$ ~ $high$를 삼등분한 지점을 각각 $mid_1$, $mid_2$라고 둘 때,

• $f(mid_1) < f(mid_2)$: 최솟값은 두 점 사이에 있거나 $low$ ~ $mid_1$에 있음. ($mid_2$ ~ $high$ 제외)
• $f(mid_1) > f(mid_2)$: 최솟값은 두 점 사이에 있거나 $mid_2$ ~ $high$에 있음. ($low$ ~ $mid_1$ 제외)

이러한 방식으로 범위를 계속 2/3 크기로 줄여나가는 것이다.

 

구현해보기(코드)

def ternary_search(f, low, high, precision):
    while abs(high - low) >= precision:
        mid1 = (low * 2 + high) / 3
        mid2 = (low + high * 2) / 3

        if f(mid1) > f(mid2):
            low = mid1
        else:
            high = mid2

    return (low + high) / 2

 

$f$는 함수, $precision$은 허용 오차이다.

삼분 탐색을 이용하는 대표적인 문제는 백준 11662번이 있다. (사실 그냥 미분해도 풀리는 문제이긴 하다.)

 

팁

• 이분/삼분 탐색시 mid를 구할 때의 덧셈 연산으로 인해 속도 저하나 오버 플로우가 발생하는 경우가 있다.
  이 경우 식을 아래와 같이 변형하면 이를 피할 수 있다.

# 이분 탐색시
mid = low + (high - low) // 2

# 삼분 탐색시
mid1 = low + (high - low) / 3
mid2 = high - (high - low) / 3

 

• 삼분 탐색시 문제에서 주어진 허용 오차를 그대로 사용하면 부동 소수점 오차로 인해 오답 처리될 수도 있다.
  주어진 오차보다 더 작은 값을 사용하거나, 아예 for문을 사용해 삼분 탐색 진행 횟수를 지정해주는 방법으로 해결할 수 있다.