이진 탐색 이론

bisect이진 탐색이란, 기존의 하나하나 검사하는 탐색 방법보다 더 빠른 탐색 알고리즘이다. 원래대로라면 길이가 N인 배열에서 어떠한 원소를 찾고자 한다면, 처음부터 N개의 원소를 하나하나 검사해보는 방식으로 탐색을 한다. 따라서 기존의 탐색 시간복잡도는 O(N)이다. 하지만 배열이 정렬되어 있다는 가정 하에 이진 탐색은 더 빠른 시간복잡도를 보장한다.

이진탐색이란?

이진탐색이란 정렬되어있는 배열에서 특정 값을 찾는 방법이다. 찾고자 하는 값을 target이라고 할 때, 배열의 중간 위치의 값이 target보다 작은지 큰지를 검사한다. 배열을 반으로 나눈 후 중간 위치의 값이 target보다 작다면 뒤의 배열에서 같은 방식으로 탐색을 반복하고, 크다면 앞의 배열에서 같은 방식으로 탐색을 반복한다.

길이가 10인 배열에서 숫자 4를 찾는다고 가정해보자. 아래의 그림을 보자.

출처 : 이것이 코딩테스트다 강의 그림

시작 인덱스 0과 끝 인덱스 9를 정한 후 중간 위치를 살펴보자. 중간점은 8이므로 목표인 4보다 크다. 따라서 시작 인덱스를 0, 끝 인덱스를 3으로 정한 후 다시 한번 살펴본다. (중간점은 div연산으로 구한다. mid = (9 + 0) // 2)

출처 : 이것이 코딩테스트다 강의 그림

시작 인덱스가 0, 끝 인덱스가 3이면 중간 인덱스는 1이 된다. 중간점은 2이고 목표는 4이므로 뒤의 배열에서 다시 탐색을 진행한다.

출처 : 이것이 코딩테스트다 강의 그림

시작 인덱스가 2, 끝 인덱스가 3이면 중간 인덱스는 2가 된다. 중간점은 목표인 4이므로 탐색을 종료한다.

이렇게 되면 계속해서 절반씩 나눠서 탐색을 하게 된다. 따라서 log_2N번의 탐색을 하게 된다. 즉 시간복잡도는 O(logN)이 된다.

 

코드 구현

직접 코드를 구현해보았다. 아래는 재귀함수를 이용해서 코드를 구현해보았다.

array = [0,1,2,3,4,5,6,7,8,9]
target = 5

def binarySearch(start, end):
    # target 예외처리
    if (start > end):
        return -1
    middle = (start + end) // 2
    print("middle :", middle)
    # target을 찾음
    if array[middle] == target:
        return middle
    # target보다 작음
    elif array[middle] < target:
        return binarySearch(middle + 1, end)
    # target보다 큼
    elif array[middle] > target:
        return binarySearch(start, middle - 1)
        
print(binarySearch(0, len(array) - 1))

퀵 정렬과 비슷한 형태의 코드가 완성되었다. 인덱스를 파라미터로 넘겨주고, 왼쪽 배열을 탐색하거나 오른쪽 배열을 탐색하여 계속 절반씩 나눠간다.

 

아래는 반복문을 이용하여 구현한 코드이다.

array = [0,1,2,3,4,5,6,7,8,9]
target = 5

# 초기화
start, end = 0, len(array) - 1
middle = (start + end) // 2
# 타겟을 찾을 때 까지
while (array[middle] != target):
    print(middle)
    # 예외 처리
    if start > end:
        middle = -1
        break
    if array[middle] < target:
        start = middle + 1
    else :
        end = middle - 1
    middle = (start + end) // 2
print(middle)

타겟을 찾을 때 까지 반복하며, 타겟에 없다면 start와 end가 같아져 예외처리 코드에서 break된다.

 

 

파이썬에는 이진 탐색을 지원하는 bisect라는 라이브러리가 있다. bisect라이브러리의 bisect_left, bisect_right함수에 대해 알아보자.

 

두 함수는 배열과 찾고자 하는 타겟을 파라미터로 받는다. 찾고자 하는 타겟이 여러 개 있을 수 있기 때문에 두 함수가 존재하는 것이다.

bisect_left는 배열에서 가장 앞에 있는 타겟의 인덱스를 반환한다. bisect_right는 가장 뒤에 있는 타겟의 인덱스 + 1을 반환한다. 정확히 말하면 타겟을 가장 왼쪽에 넣는다면 어느 위치에 넣을 수 있는지, 가장 오른쪽에 넣는다면 어느 위치에 넣을 수 있는지를 반환해주는 함수이다.

from bisect import bisect_left, bisect_right

array = [1,2,3,3,3,4]
target = 3

print(bisect_left(array, target)) # 2
print(bisect_right(array, target)) # 5

 

파라메트릭 서치는 어떠한 문제를 예 아니오로 결정될 수 있는 문제로 바꾸어서 차례로 해결해나가는 방식이다. 실제로 파라메트릭 서치는 이진탐색으로 해결한다.