파이썬 bisect 모듈로 마스터하는 이분 탐색 알고리즘

이분 탐색(bisect) 알고리즘은 정렬된 리스트 안에서 데이터를 삽입해도 정렬 상태가 유지되는 위치를 찾는 데 사용됩니다. 파이썬에는 이러한 기능을 제공하는 전용 모듈인 bisect가 기본으로 포함되어 있어, 별도의 구현 없이도 효율적인 이분 탐색을 활용할 수 있습니다.

bisect 모듈의 핵심 함수들은 시간 복잡도 O(log n)으로 동작하기 때문에, 대용량의 정렬된 데이터에서 삽입 위치를 찾을 때 선형 탐색보다 훨씬 빠른 성능을 보여줍니다.

bisect 모듈 임포트하기

모듈을 사용하려면 먼저 다음과 같이 임포트해야 합니다.

import bisect

bisect 모듈의 주요 함수

1. bisect.bisect(list, element, begin, end)

정렬된 리스트에서 지정한 요소를 삽입할 수 있는 위치를 찾아 반환합니다. 삽입 후에도 리스트는 계속 정렬 상태를 유지합니다. 만약 동일한 값이 이미 존재한다면, 삽입 가능한 위치 중 가장 오른쪽(뒤쪽) 위치를 반환합니다.

2. bisect.bisect_left(list, element, begin, end)

bisect() 함수와 동일하게 동작하지만, 한 가지 차이점이 있습니다. 동일한 요소가 이미 존재하는 경우 가장 왼쪽(앞쪽) 위치를 반환합니다.

3. bisect.bisect_right(list, element, begin, end)

bisect() 함수와 완전히 동일하게 동작합니다. 즉, 동일한 값이 있으면 오른쪽 위치를 반환합니다.

4. bisect.insort(list, element, begin, end)

위치만 반환하는 bisect()와 달리, 요소를 올바른 위치에 실제로 삽입한 뒤 정렬된 리스트를 유지합니다. 동일한 값이 이미 존재하면 가장 오른쪽 위치에 삽입됩니다.

5. bisect.insort_left(list, element, begin, end)

insort() 함수와 동일하지만, 동일한 요소가 이미 존재하는 경우 가장 왼쪽 위치에 삽입한다는 점이 다릅니다.

6. bisect.insort_right(list, element, begin, end)

insort() 함수와 완전히 동일하게 동작합니다.

참고: 매개변수 begin과 end는 선택 사항으로, 탐색 범위를 리스트의 특정 구간으로 제한하고 싶을 때 사용합니다. 생략하면 리스트 전체가 탐색 대상이 됩니다.

예제 코드

import bisect

my_list = [11, 25, 36, 47, 56, 69, 69, 69, 78, 78, 91, 102, 120]

# 53을 삽입할 적절한 위치 찾기
print('53을 삽입할 올바른 위치:', str(bisect.bisect(my_list, 53, 0, len(my_list))))

# 중복값 69의 오른쪽/왼쪽 삽입 위치 비교
print('69를 삽입할 올바른 오른쪽 위치:', str(bisect.bisect_right(my_list, 69, 0, len(my_list))))
print('69를 삽입할 올바른 왼쪽 위치:', str(bisect.bisect_left(my_list, 69, 0, len(my_list))))

# insort로 실제 삽입 수행
bisect.insort(my_list, 59, 0, len(my_list))
print(my_list)

bisect.insort_left(my_list, 78, 0, len(my_list))
print(my_list)

실행 결과

53을 삽입할 올바른 위치: 4
69를 삽입할 올바른 오른쪽 위치: 8
69를 삽입할 올바른 왼쪽 위치: 5
[11, 25, 36, 47, 56, 59, 69, 69, 69, 78, 78, 91, 102, 120]
[11, 25, 36, 47, 56, 59, 69, 69, 69, 78, 78, 78, 91, 102, 120]

결과 해석

값 53은 47과 56 사이, 즉 인덱스 4에 삽입되어야 정렬이 유지됩니다.
중복된 값 69가 세 개 존재할 때, bisect_right()는 인덱스 8(중복 구간의 끝)을, bisect_left()는 인덱스 5(중복 구간의 시작)를 반환합니다.
insort() 실행 후 59가 올바른 자리에 추가되었고, insort_left() 실행 후 78이 기존 78들 앞쪽에 삽입된 것을 확인할 수 있습니다.

이처럼 파이썬의 bisect 모듈을 활용하면 정렬된 리스트에서 삽입 위치 탐색과 삽입 작업을 간결하고 효율적으로 처리할 수 있습니다.

파이썬 bisect 모듈로 마스터하는 이분 탐색 알고리즘 – 정렬된 리스트 삽입 위치 찾기