bisect는 「정렬된 리스트에서 특정 값의 삽입 위치를 빠르게(O(log n)) 찾는」 표준 모듈입니다.
정렬을 유지하며 새 값을 추가하거나, 정렬된 리스트에서 빠른 검색이 필요할 때 결정적입니다.
기본 사용.
import bisect.
sorted_nums = [1, 3, 5, 7, 9].
bisect.bisect_left(sorted_nums, 5) — 값 5가 들어갈 가장 왼쪽 위치(2).
bisect.bisect_right(sorted_nums, 5) — 가장 오른쪽 위치(3).
bisect.insort(sorted_nums, 4) — 정렬 유지하며 4 삽입.
활용 예시 1: 등급 매기기.
grades = [60, 70, 80, 90].
labels = ["F", "D", "C", "B", "A"].
score = 75.
labels[bisect.bisect_right(grades, score)] — 75는 70~80 사이라 "C"가 반환.
점수 등급 같은 「임계값 기반 분류」에 매우 효율적.
활용 예시 2: 정렬 유지.
heapq처럼 매번 정렬할 필요 없이 「추가될 때마다 정렬된 상태 유지」가 필요한 경우 insort가 답입니다.
시계열 데이터, 우선순위 정렬 같은 자리에서 표준입니다.
주의할 점은 「리스트가 정렬돼 있어야 한다」는 전제입니다.
정렬되지 않은 리스트에 bisect를 쓰면 결과가 무의미합니다.
또 list.insert(i, x)는 O(n) 비용이 들어 매우 큰 리스트에서는 SortedList(third-party 라이브러리)를 쓰는 게 더 나은 선택일 수 있습니다.
한 줄 요약
bisect는 정렬된 리스트에서 O(log n) 이진 검색·삽입을 제공합니다.
등급 매기기·임계값 분류·정렬 유지 삽입에 결정적이며, 리스트가 항상 정렬돼 있어야 합니다.
더 알아볼 것
- bisect_left vs bisect_right의 차이
- SortedList — sortedcontainers 라이브러리
- 이진 검색의 직접 구현 vs bisect
