이진 탐색

이진 탐색 (binary search)

이진 탐색은 이미 정렬되어 있는 배열에서 원하는 값을 빠르게 찾고 싶을 때 사용한다.

 

 

이진 탐색은 업 앤 다운 게임을 생각하면 이해하기 쉽다.

 

https://namu.wiki/w/업%20앤%20다운

 

1이상 50 이하인 수를 맞추는 게임에서 25를 선택했는데 정답이 25보다 작다고 해보자.

 

다음 선택지의 범위는 1 이상 24 이하가 될 것이다.

 

항상 중간에 있는 값을 선택할 경우 범위가 계속 반 정도로 줄어들기 때문에 최악의 경우에도(정답이 1인 경우에도) 6번이면($\because log(50) \approx 5.64$) 정답을 맞추게 된다.

 

 

이진 탐색의 수행 과정을 예시를 통해 구체적으로 알아보자.

 

1.

 

이미 정렬된 배열 a = [1, 1, 2, 2, 2, 3, 4, 5, 5, 5]가 주어졌다고 하자.

 

우리가 찾고자 하는 값이 3 이라고 하자.

 

start = 0, end = 9 로 놓는다.

 

중앙값 mid = (0 + 9) // 2 = 4 를 계산한다.

 

a[4] = 2 는 3보다 작다.

 

이제 우리는 mid+1 = 5번째 항부터 9번째 항까지만 고려하면 된다. 즉, 정답은 [3, 4, 4, 5, 5] 안에 있다.

 

start = mid+1 = 5, end = 9 로 놓는다.

 

중앙값 mid = (5 + 9) // 2 = 7 을 계산한다.

 

a[7] = 5 는 3보다 크다.

 

이제 우리는 5번째 항부터 mid-1 = 6번째 항까지만 고려하면 된다. 즉, 정답은 [3, 4] 안에 있다.

 

start = 5, end = mid - 1 = 6 으로 놓는다.

 

중앙값 mid = (5 + 6) // 2 = 5 를 계산한다.

 

a[5] = 3 은 우리가 찾고자 하는 값이다!

 

2.

 

이미 정렬된 배열 a = [1, 1, 2, 2, 4, 4]이 주어졌다고 하자.

 

우리가 찾고자 하는 값이 3 이라고 하자.

 

start = 0, end = 5 로 놓는다.

 

중앙값 mid = (0 + 5) // 2 = 2 를 계산한다.

 

a[2] = 2 는 3보다 작다.

 

이제 우리는 mid + 1 = 3번째 항부터 5번째 항까지만 고려하면 된다. 즉, 정답은 (있다면) [2, 4, 4] 안에 있다.

 

start = 3, end = 5 로 놓는다.

 

중앙값 mid = (3 + 5) // 2 = 4 를 계산한다.

 

a[4] = 4 는 3보다 크다.

 

이제 우리는 3번째 항부터 mid - 1 = 3번째 항까지만 고려하면 된다. 즉, 정답은 (있다면) [2] 안에 있다.

 

이 시점에서 우리는 a[3] = 2 이므로 우리가 찾고자 하는 값 3이 배열 안에 없다는 사실을 알 수 있다.

 

물론, 이 부분을 start == end and a[mid] != 3 조건으로 따로 확인해도 된다.

 

하지만, 다음 과정을 그대로 진행하면 어짜피 start = 3, end = 2 가 되어 start > end 가 되고, 이 부분을 자연스러운 종료 조건으로 사용할 수 있다.

 

소스 코드 (반복문 이용)

def binary_search(a, target):
    start, end = 0, len(a)-1

    while start <= end:
        mid = (start+end)//2

        if a[mid] == target:
            return mid
        elif a[mid] < target: # target이 더 오른쪽
            start = mid + 1
        elif a[mid] > target: # target이 더 왼쪽
            end = mid - 1
            
    return None

 

소스 코드 (재귀 함수 이용)

def binary_search(a, target, start, end):
    if start > end:
        return None

    mid = (start+end)//2

    if a[mid] == target:
        return mid
    elif a[mid] < target: # target이 더 오른쪽
        return binary_search(a, target, mid+1, end)
    elif a[mid] > target: # target이 더 왼쪽
        return binary_search(a, target, start, mid-1)

 

수행 시간 : $O(\log n)$

 

 

추가로, 이진 탐색은 이미 정렬된 배열에서 특정 값의 count를 빠르게 셀 때에도 활용할 수 있다.

 

예를 들어, a = [1, 1, 2, 2, 2, 2, 3, 4, 4] 에 대해 2의 개수를 세고 싶다면

 

2의 minimal index를 찾는 이진 탐색과 2의 maximal index를 찾는 이진 탐색을 각각 수행하고

 

max_idx - min_idx + 1 = 5 - 2 + 1 로 정답을 구할 수 있다.

 

 

소스 코드 ( 직접 구현 )

 

# target의 가장 작은 index 구하기
min_idx = int(1e9)
start, end = 0, len(a)-1
while start <= end:
    mid = (start + end)//2

    if a[mid] == target: # 왼쪽에도 target이 있는지 확인
        min_idx = mid
        end = mid - 1
    elif a[mid] > target: # target이 더 왼쪽에 있음
        end = mid - 1
    else: # target이 더 오른쪽에 있음
        start = mid + 1

# target의 가장 큰 index 구하기
max_idx = int(1e9)
start, end = 0, len(a) - 1
while start <= end:
    mid = (start + end) // 2

    if a[mid] == target:  # 오른쪽에도 target이 있는지 확인
        max_idx = mid
        start = mid + 1
    elif a[mid] > target:  # target이 더 왼쪽에 있음
        end = mid - 1
    else: # target이 더 오른쪽에 있음
        start = mid + 1

print(max_idx - min_idx + 1)

 

 

소스코드 ( bisect 라이브러리 사용 )

 

from bisect import bisect_left, bisect_right

print(bisect_right(a, target) - bisect_left(a, target))