배열에서 어떤 값을 찾고 싶을 때, 단순하게 처음부터 끝까지 값이 같은지 확인하는 방법이 있다.

그러나 이는 배열의 크기가 커질수록 걸리는 시간이 선형적으로 비례해 높아지는데, 이보다 더 효율적인 방법이 존재한다.

만약 배열이 정렬된 상태일 경우에는 이진 탐색을 통해 훨씬 더 빠르게(log N만에) 값을 찾아낼 수 있다.

개념

log N 만에 찾는다는 것은, 만약 값이 30개가 있으면 약 5번만에, 4000개가 있으면 약 12번만에, 100만개가 있으면 약 20번만에 찾아낼 수 있다는 뜻이다.

이진 탐색은 찾으려는 값보다 작거나 큰 값들은 굳이 확인하지 않는다는 마인드이다.

우리가 찾으려는 값이 X 라고 한다면, 배열이 정렬된 상태이기 때문에, 특정 위치를 확인한 뒤 해당 위치의 값이 X보다 작을 경우, 그 위치 이전에 있는 모든 값들을 확인하지 않아도 무방하다.

그렇기 때문에 이러한 특정 위치를 어떻게 잡느냐에 따라서 확인하지 않아도 되는 값들을 얼마나 줄일 수 있는지가 결정된다.

만약 해당 위치를 단순히 앞에서부터 하나씩 증가시킬 경우네는 선형 탐색과 달라질 것이 없기 때문이다.

이진 탐색은 이 위치를 현재 배열 탐색 범위의 절반으로 잡아서, 찾으려는 값이 속한 절반을 제외한 나머지 절반을 다음 탐색에서 제외시킨다.

즉, 1000개의 값을 갖는 정렬된 배열이 있고 실제로 찾으려는 값이 300번째 위치에 있다고 한다면, 처음에는 500번째 값을 확인해서 500~1000 번째 값들을 날려버리는 것이다.

이렇게 될 경우 첫 탐색에서 500개, 두번째 탐색에서는 250개, 세번째 탐색에서는 125개를 제외시켜나가면서 값이 존재할 수 있는 범위를 절반씩 좁혀나간다.

절반씩 범위가 줄기 때문에, 찾으려는 값에 log N 만에 도달할 수 있는 것이다.

Lower Bound / Upper Bound

만약에 배열에 하나의 값이 여러번 중복해서 존재한다고 하면, 찾으려는 값이 이 배열에 몇 개 존재하는지를 알고 싶을 수도 있다.

이럴 때 찾으려는 값이 처음 등장하는 인덱스(lower bound)와, 찾으려는 값이 끝나는 인덱스(다음 값이 처음 등장하는 인덱스, upper bound)를 알 수 있다면, 이 둘의 차이를 가지고 해당 값의 개수를 파악할 수 있다.

즉, Lower Bound 함수는 이진 탐색을 진행하면서 값을 찾으면 종료하는 것이 아닌, 배열에서 "해당 값보다 같거나 큰 값"이 처음 나오는 위치를 찾는다.

Upper Bound 는, 처음으로 "해당 값보다 큰 값"이 나오는 위치를 찾는다.

파이썬 코드

# 정렬된 배열 arr 에서 값을 찾을 경우 바로 인덱스를 반환하는 이진탐색
def binary_search(arr, val):
    ldx, rdx = 0, len(arr)-1
    # 전부 검사했는데 값이 없을 경우 while 종료되며 None 반환
    while ldx <= rdx:
        # ldx 와 rdx 의 중간지점을 짚어서 절반씩 탐색 범위를 줄임
        mdx = (ldx + rdx) // 2
        if arr[mdx] < val:
            ldx = mdx + 1
        elif arr[mdx] > val:
            rdx = mdx - 1
        else:
            return mdx
    return None

Lower / Upper Bound

def lower_bound(arr, val):
    ldx, rdx = 0, len(arr)
    while ldx < rdx:
        mdx = (ldx + rdx) // 2
        if arr[mdx] >= val:
            rdx = mdx
        else:
            ldx = mdx + 1
    return ldx

def upper_bound(arr, val):
    ldx, rdx = 0, len(arr)
    while ldx < rdx:
        mdx = (ldx + rdx) // 2
        if arr[mdx] <= val:
            ldx = mdx + 1
        else:
            rdx = mdx
    return ldx

예시

아래 그림에서 배열이 정렬된 상태이기 때문에, 4가 존재한다면 어느 인덱스에 위치하는지를 이진 탐색으로 알아볼 수 있다.

• 먼저 ldx 는 왼쪽 끝인 인덱스 0번, rdx는 오른쪽 끝인 인덱스 9번으로 초기화된 뒤 탐색이 시작된다.

• mdx 는 ldx 와 rdx 의 절반 위치로, mdx = (ldx + rdx) // 2에 의해 mdx = 4 가 되고, mdx 에 해당하는 값은 배열에서 4번 인덱스에 위치한 8이 된다.

• 찾으려는 값 4는 8보다 작기 때문에, 배열에서 8 이상의 값을 갖는 범위를 다음 탐색에서 제외시킬 수 있다. 즉, 다음 탐색의 범위는 인덱스 0 ~ 3 까지로 줄어든다.

• mdx 역시 8 이상이므로 다음 탐색에서 제외시킬 수 있기 때문에, rdx = mdx - 1를 통해 ldx 는 그대로 0, rdx 는 3이 되어 탐색 범위가 설정된 뒤 while 문을 다시 수행한다.

• ldx=0 과 rdx=3 에 의해 이번 반복에서의 mdx 값은 1이 되고, mdx 의 값인 2 는 찾으려는 값 4보다 작기 때문에 이번 반복에서는 2 이하의 값을 갖는 범위를 제외시킨다.

• 이번에는 if arr[mdx] < val:에 걸리는 것이기 때문에, ldx의 값을 mdx + 1 로 설정해줌으로써 ldx=2, rdx=3 이 된 뒤 다음 반복을 수행한다.

• 이번 mdx 값은 (2 + 3) // 2 로 mdx=2 가 되며, mdx 위치에 해당하는 값이 우리가 찾으려는 값 4와 같기 때문에 mdx 를 반환하며 이진 탐색은 종료된다.

• 지금은 찾는 값이 있기 때문에 배열을 절반씩 줄여나가면서 log(N) 만에 값을 찾았지만, 만약 찾는 값이 없다고 할 경우에도 나머지 탐색을 실시하다가 while 문이 종료되어 return None으로 종료된다.

• 예를 들어 우리가 찾으려는 값이 4가 아니고 5라고 했을 때, 마지막 루프에서는 mdx=2 의 값인 4가 타겟인 5보다 작으므로 ldx 가 3으로 설정된 뒤 다음 루프로 넘어간다.

• ldx=3, rdx=3 인 상태에서 mdx=3 이 되고, 3번째 값인 6은 5보다 크기 때문에 rdx가 2로 설정되고 다음 루프로 넘어가는데, 이 때 while ldx <= rdx 조건에서 걸리며 반복문이 종료되는 것이다.