이분 탐색과 Python의 bisect_left

이분 탐색 vs. 순차적 탐색

이분 탐색(binary search)란, 어떤 배열과 찾고자 하는 수가 있을 때, 찾고자 하는 범위를 절반씩 좁혀가며 빠르게 해당 값의 위치를 찾아내는 알고리즘입니다. 알고리즘 문제에서 자주 등장하는 대표적인 탐색 기법으로, 단순한 정렬 배열 탐색부터, 경계값 찾기, 응용 문제까지 매우 다양한 형태로 출제됩니다. 매 반복마다 검색 범위를 절반으로 줄이기에 O(log n)의 시간 복잡도를 가집니다. 다만, 값의 대소를 비교하며 범위를 잡기에 배열이 반드시 정렬됨을 전제로 합니다.

구현: 반복 vs. 재귀

이분 탐색은 먼저 시작 인덱스와 끝 인덱스를 잡고, 그 둘의 중간 (또는 안 나눠떨어질 경우 한 칸 왼쪽) 인덱스를 잡는 것으로 시작합니다. 그리고 정확한 값의 인덱스를 찾을 때까지 시작, 중간, 끝 인덱스를 아래와 같이 계속 조정하는 것으로 이루어집니다. 

반복으로 구현하기

백문이 불여일견, 반복으로 구현된 Python 코드를 보시겠습니다.

def binary_search_itr(arr, target): # arr: 전체 배열, target: 찾고자 하는 값
    left = 0
    right = len(arr) - 1  # 검색 범위는 [left, right]

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid  # 값을 찾았으면 해당 인덱스 반환
        elif arr[mid] < target:
            left = mid + 1  # 오른쪽 구간으로 이동
        else:
            right = mid - 1  # 왼쪽 구간으로 이동

    return -1  # 값을 찾지 못했을 경우

가령, [1, 3, 4, 5, 7, 9, 11, 22, 33, 44, 55, 66]라는 배열이 있고, 찾고자 하는 값은 22이라고 가정하여, 아래와 같이 반복문을 따라가봅시다.

반복문 따라가기

반복문에 처음 들어오면 left=0, right=11입니다. 그리고 mid는 (0+11)//2, 즉 5가 됩니다. 이는 곧 0부터 11까지의 인덱스를 범위로 잡고, 그 가운데의 숫자를 target(=22)과 비교하는 것입니다. arr[5]=9이므로, 22보다 작습니다. 즉 시작점인 left 값을 mid+1, 즉 6으로 조정합니다. 반복문 마지막에 left, mid, right는 각각 6, 5, 11로 조정됩니다.

두 번째 반복에서 left=6, right=11로 시작합니다. 그리고 mid는 (6+11)//2, 즉 8입니다. 다시 말해, 6부터 11까지의 인덱스를 범위로 잡고, 그 가운데의 숫자를 target(=22)과 비교하는 것입니다. arr[8]=33이므로, 22보다 큽니다. 이번에는 끝점인 right값을 mid-1, 즉 7로 조정합니다. 반복문 마지막에 left, mid, right는 각각 6, 8, 7로 조정됩니다.

세 번째 반복에서 left=6, right=7로 시작합니다. 그리고 mid는 (6+7)//2, 즉 6입니다. 다시 말해, 6부터 7까지의 인덱스를 범위로 잡고, 그 가운데의 숫자를 target(=22)과 비교하는 것입니다. arr[6]=11이므로, 22보다 작습니다. 이번에는 시작점인 left 값을 mid+1, 즉 7로 조정합니다. 반복문 마지막에 left, mid, right는 각각 7, 6, 7로 조정됩니다.   

네 번째 반복에서도 위와 동일한 과정으로, left=7, mid=7, right=7로 시작합니다. 셋 다 같은 값이니 `if arr[mid] == target` 조건에 걸립니다. 값을 찾았습니다. arr[7]=22. 이제 mid의 7을 리턴함으로써 함수가 종료됩니다.

재귀로 구현하기

아래는 동일한 기능을 재귀로 구현한 코드입니다.

def binary_search_rcv(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1  # 최초 호출 ==> right 초기화

    if left > right:
        return -1  # base case && 값이 없음

    mid = (left + right) // 2

    if arr[mid] == target:
        return mid  # base case && 값이 있음 => 해당 인덱스 리턴
    elif arr[mid] < target:
        return binary_search_rcv(arr, target, mid + 1, right)  # 오른쪽 구간에서 재귀
    else:
        return binary_search_rcv(arr, target, left, mid - 1)   # 왼쪽 구간에서 재귀

이를 기반으로 풀 수 있는 문제가 바로 백준 10815 "숫자 카드"입니다. https://www.acmicpc.net/problem/10815

참고로 아래는 naive approach로 구현한 코드인데, 혹-시 if in 문법이 나름의 최적화를 거쳐서 답을 빠르게 찾아내지 않을까 했으나, 시간 초과가 납니다.

import sys
input = sys.stdin.readline

cards_count = int(input())
cards_in_pkt = sorted(map(int,input().split()))
tests_count = int(input())
tests = list(map(int,input().split()))

result = [1 if a in cards_in_pkt else 0 for a in tests]
print(*result)

 

응용: 정확한 값이 없을 경우, '최소의 최대' 문제

간혹 정확한 타깃이 주어지지 않는 문제들이 있습니다. 바로 백준 2805 "나무 자르기"와 같은 문제들입니다.

마지막 문단에 나온 바와 같이, "적어도 M미터를 보장하는 절단기의 높이의 최댓값"을 구하는 문제입니다. 정확한 타깃을 찾는 게 아니라 가능한 값 중 최대를 구하는 것입니다. 이러한 경우 이분 탐색은 아래와 같이 응용될 수 있습니다.

count, target_num = map(int,input().split())
trees = list(map(int,input().split()) )

low, high = 0, max(trees)

while low <= high:
    mid = (low + high) // 2
    sum_cut = sum((trees[i] - mid) for i in range(len(trees)) if trees[i] > mid)
    if sum_cut >= target_num: 
        low = mid + 1 # 더 많다 ==> low를 갱신
    else:
        high = mid - 1 # 모자라다 ==> high를 갱신

print(result)

이는 전형적인 parametric search (파라메트릭 서치) 문제로, 조건을 만족하는 최댓값을 찾는 'upper bound' 패턴이기에 아래 설명 드릴 `bisect_right`와 동일한 기능을 수행합니다.

bisect_left vs. bisect_right

Python 내장 모듈 중 `bisect`는 정렬된 리스트에 값을 삽입하거나 위치를 찾는 함수들을 제공합니다. 대표적으로는 `bisect`, `bisect_left`, `bisect_right`가 있겠습니다. 

핵심 함수 비교

함수	반환 위치	의미
bisect_left(a, x)	왼쪽 삽입 위치	x를 넣을 수 있는 가장 왼쪽 위치
bisect_right(a, x) 또는 bisect(a, x)	오른쪽 삽입 위치	x를 넣을 수 있는 가장 오른쪽 위치

참고: `bisect()`는 `bisect_right()`의 alias, 즉, 같은 함수입니다.

아래와 같이 작성한 코드를 통해 비교해봅시다.

def bs_by_bisect(arr,target_num):
    return (bisect_left(arr,target_num), bisect(arr,target_num), bisect_right(arr,target_num))
    
arr = [10, 20, 50, 66, 123, 214, 333, 444, 555, 777]
print("----------------------")
target_num = 49
print("target_num:",target_num, bs_by_bisect(arr,target_num))
target_num = 50
print("target_num:",target_num, bs_by_bisect(arr,target_num))
target_num = 51
print("target_num:",target_num, bs_by_bisect(arr,target_num))
print("----------------------")

결과는 위와 같습니다.

`bisect_left`는 49와 50에서 인덱스 2, 즉 20의 위치를 리턴합니다. 그리고 51이 되어서야 50의 위치를 리턴합니다. 반면 `bisect_right`는 49에서만 20의 위치를 리턴하며, 50부터는 바로 50의 위치를 리턴합니다.

더 나아가기

지금까지 이분 탐색의 개념으로부터 시작하여 `bisect_left`, `bisect_right` 등 이들의 개념을 응용한 유형까지 알아보았습니다. 아래는 백준 11053 "가장 긴 증가하는 부분 수열"입니다. 이분 탐색을 응용하여 직접 구현해보시기를 추천 드립니다.

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