이분 탐색

Binary Search

개요

정렬된 곳에서 값을 찾을 때, 찾는 부분에서 중앙값이 찾는 값 보다 큰지 작은지를 이용해서 범위를 반씩 줄여나가는 탐색 방법입니다.

구현

오름차순으로 정렬된 배열에서 중앙값이 찾는 값 보다 크다면, 우리가 찾으려는 값은 중앙값보다 왼쪽에 있을 것이고, 작다면 오른쪽에 있을 것입니다.

찾으려는 구간을 lo에서 hi까지라고 합시다. mid = (lo + hi) / 2라 하면 찾으려는 값 x가 중앙값arr[mid]보다 크다면 lo = mid + 1로 지정해 x보다 작은 부분 0 ~ mid을 제외합니다. x가 중앙값 arr[mid]보다 작다면 hi = mid - 1로 지정해 x보다 큰 부분 mid ~ len(arr)-1을 제외합니다.

def binary_search(arr, x):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < x:
            lo = mid + 1
        elif x < arr[mid]:
            hi = mid - 1
        else:
            return mid
    return -1 # 못 찾음

시간 복잡도

찾는 범위의 크기를 이라 했을 때, 중앙값을 기준으로 반씩 줄여나가면 번 만에 찾을 수 있으므로 시간 복잡도는 이 됩니다.

lower/upper bound

lower bound는 처음으로 크거나 같은 원소가 나타나는 인덱스를 찾습니다. upper bound는 처음으로 큰 원소가 나타나는 인덱스를 찾습니다.

def lower_bound(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < x: # 미만인 부분 제외
            lo = mid + 1
        else:
            hi = mid
    return start
 
def upper_bound(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] <= x: # 이하인 부분 제외
            lo = mid + 1
        else:
            hi = mid
    return lo

문제

• 2805번: 나무 자르기 풀이
  대부분의 프로그래밍 언어는 배열에서의 이분 탐색을 지원하지만, 그럼에도 우리가 이분 탐색을 구현할 수 있어야 하는 이유는 매개 변수 탐색 문제를 풀기 위해서입니다.