[Python] bisect 모듈

Python bisect 모듈

bisect는 정렬된 리스트에 원소를 효율적으로 삽입하거나, 이진 탐색을 수행할 때 사용하는 파이썬 내장 모듈

• 시간복잡도: O(log n)
• 정렬된 리스트의 삽입 위치를 빠르게 찾을 때 사용
• 직접 이진 탐색을 구현할 필요 없이 간편하게 해결 가능

주요 함수

함수명	설명
bisect.bisect_left(a, x)	정렬된 리스트 a에서 x를 삽입할 가장 왼쪽 위치 반환
bisect.bisect_right(a, x) / bisect.bisect(a, x)	x를 삽입할 가장 오른쪽 위치 반환
bisect.insort_left(a, x)	x를 왼쪽 기준 위치에 삽입
bisect.insort_right(a, x) / bisect.insort(a, x)	x를 오른쪽 기준 위치에 삽입

사용 예시

• 정렬된 배열에서 원소의 삽입 위치가 필요할 경우
• 중복 원소 포함 여부 확인이나 개수 세기
• Lower bound / Upper bound 구현
• 정렬된 데이터를 유지한 채 삽입이 반복되는 상황

사용 예시 - 코드

• bisect_left: 4가 처음 나오는 위치(idx: 2)
• bisect_right: 4가 끝나는 위치(idx: 4)
• insort: 적절한 위치에 삽입(리스트가 여전히 정렬된 상태를 유지)

import bisect

arr = [1, 3, 4, 4, 5]

print(bisect.bisect_left(arr, 4))   # ➜ 2
print(bisect.bisect_right(arr, 4))  # ➜ 4

# 삽입
bisect.insort(arr, 4)
print(arr)  # ➜ [1, 3, 4, 4, 4, 5]

시간복잡도

• bisect_left, bisect_right: O(log n)
• insort_left, insort_right: O(n) → 삽입 자체는 O(n) (리스트 이동이 필요)