[파이썬 100강] 66강. bisect로 정렬 리스트에 빠르게 삽입·탐색하기

정렬된 리스트에서 값이 들어갈 위치를 매번 for문으로 찾기 시작하면, 코드도 길어지고 경계값 버그도 자주 납니다. 이번 강의에서는 bisect로 정렬 상태를 유지한 채 위치를 찾고 삽입하는 방법을 익힙니다.

---

핵심 개념

• bisect는 정렬된 시퀀스에서 이진 탐색(binary search) 으로 삽입 위치를 빠르게 찾는 표준 모듈입니다.
• bisect_left와 bisect_right는 중복 값이 있을 때 어디에 꽂을지 규칙이 다릅니다.
• insort_left/insort_right는 위치 탐색 + 삽입을 한 번에 처리해 정렬 상태를 자동 유지합니다.

리스트를 정렬해 두고 계속 값을 넣거나 구간을 찾는 작업은 실무에서 꽤 자주 나옵니다. 예를 들어 점수 구간 분류, 시계열 데이터 삽입, 랭킹 유지 같은 문제입니다. 이때 직접 비교문을 잔뜩 써서 위치를 찾으면 <=와 < 경계가 엇갈리기 쉽고, 중복 데이터 정책도 일관되게 유지하기 어렵습니다. bisect를 쓰면 "정렬은 유지되어 있다"는 전제 아래 위치 계산을 표준화할 수 있습니다. 특히 bisect_left는 같은 값이 여러 개일 때 가장 왼쪽 위치를, bisect_right는 가장 오른쪽 다음 위치를 반환합니다. 이 차이를 이해하면 "중복 허용 정책"을 코드에서 명확하게 표현할 수 있습니다. 또 주의할 점은, 위치 찾기 자체는 빠르지만 리스트 중간 삽입은 원소 이동이 있으므로 데이터가 매우 크고 삽입이 많다면 다른 자료구조도 함께 검토해야 한다는 것입니다.

실무 연결 포인트

• 실시간 점수/가격/지연시간 같은 수치를 정렬 상태로 유지하면서 임계값 판단할 때 자주 씁니다.
• 경계값 버그(90점은 A인가 B인가)를 줄이고, 중복 처리 규칙을 코드로 고정할 수 있습니다.
• 데이터가 커질수록 "탐색 로직 재작성"보다 표준 모듈 기반 구현이 유지보수 비용을 크게 줄여줍니다.

기본 사용

예제 1) bisect_left / bisect_right 차이 이해하기

>>> import bisect
>>> scores = [60, 70, 70, 80, 90]
>>> bisect.bisect_left(scores, 70)
1
>>> bisect.bisect_right(scores, 70)
3
>>> bisect.bisect_left(scores, 75)
3
>>> bisect.bisect_right(scores, 75)
3

해설:

• 값 70이 이미 2개 있으므로 left는 첫 70의 인덱스(1), right는 마지막 70의 다음(3)을 돌려줍니다.
• 값이 없는 75는 두 함수 모두 같은 삽입 위치(3)를 줍니다.
• 중복 허용 정책을 정할 때 left/right를 의도적으로 선택해야 합니다.

예제 2) insort로 정렬 상태 자동 유지하기

>>> import bisect
>>> data = [10, 20, 40, 50]
>>> bisect.insort_left(data, 30)
>>> data
[10, 20, 30, 40, 50]
>>> bisect.insort_right(data, 40)
>>> data
[10, 20, 30, 40, 40, 50]

해설:

• insort_left는 같은 값이 있으면 왼쪽에 삽입하고, insort_right는 오른쪽에 삽입합니다.
• "항상 정렬 유지"가 필요한 경우 삽입 시점마다 sort()를 다시 호출하는 비용과 실수를 줄여줍니다.

예제 3) 구간 분류(등급 컷) 구현하기

>>> import bisect
>>> cutoffs = [60, 70, 80, 90]  # 각 경계 이상이면 다음 등급
>>> labels = ["F", "D", "C", "B", "A"]
>>> def grade(score):
...     idx = bisect.bisect_right(cutoffs, score)
...     return labels[idx]
...
>>> [grade(s) for s in [59, 60, 69, 70, 89, 90, 100]]
['F', 'D', 'D', 'C', 'B', 'A', 'A']

해설:

• 경계값 판정에서 if-elif 체인을 길게 쓰지 않아도 됩니다.
• 컷오프 정책이 바뀌면 리스트만 수정하면 되므로 운영 변경이 쉽습니다.

예제 4) 범위 검색 개수 세기

>>> import bisect
>>> values = [1, 2, 2, 2, 3, 5, 8, 8, 10]
>>> left = bisect.bisect_left(values, 2)
>>> right = bisect.bisect_right(values, 8)
>>> right - left
7
>>> values[left:right]
[2, 2, 2, 3, 5, 8, 8]

해설:

• [2, 8] 구간처럼 범위 질의가 많을 때 인덱스 차이로 개수를 바로 구할 수 있습니다.
• 분석/통계 코드에서 필터 반복문을 줄이고 의도를 명확하게 표현할 수 있습니다.

자주 하는 실수

실수 1) 정렬되지 않은 리스트에 bisect 적용하기

>>> import bisect
>>> arr = [30, 10, 20]
>>> bisect.bisect_left(arr, 15)
2

원인:

• bisect는 "이미 정렬되어 있다"는 전제를 기반으로 동작합니다.
• 정렬되지 않은 상태에서는 반환 위치가 논리적으로 의미가 없습니다.

해결:

>>> arr = [30, 10, 20]
>>> arr.sort()
>>> bisect.bisect_left(arr, 15)
1
>>> arr
[10, 20, 30]

• 최초 1회 정렬 + 이후 insort로 유지하는 흐름을 습관화합니다.

실수 2) left/right 의미를 혼동해 경계값 판정이 뒤집힘

• 증상: 동일 점수에서 등급이 한 단계 밀리거나 올라감
• 원인: "이상/초과" 기준을 명확히 정하지 않고 left/right를 감으로 선택함
• 해결: 요구사항을 먼저 문장으로 고정합니다. 예) "90점 이상은 A"라면 bisect_right가 자연스럽습니다.

실수 3) 탐색이 빠르니 삽입도 항상 빠르다고 오해하기

>>> import bisect
>>> arr = [1, 3, 5, 7]
>>> pos = bisect.bisect_left(arr, 4)
>>> pos
2
>>> arr.insert(pos, 4)
>>> arr
[1, 3, 4, 5, 7]

원인:

• 위치 찾기는 이진 탐색이라 빠르지만, 리스트 중간 삽입은 뒤 원소 이동 비용이 있습니다.

해결:

• 데이터 규모와 삽입 빈도가 높으면 heapq, deque, 데이터베이스 인덱스, 또는 별도 정렬 구조를 검토합니다.
• bisect는 "정렬 리스트를 단순하고 정확하게 다룰 때" 가장 효과적입니다.

실무 패턴

• 입력 검증 규칙

  • 삽입 전 값 타입(int/float/Decimal)을 통일합니다. 문자열 숫자 혼입은 즉시 정규화합니다.
  • 정렬 기준(오름차순/내림차순)을 함수/주석으로 고정하고, 역순 데이터 유입 시 경고 로그를 남깁니다.

• 로그/예외 처리 규칙

  • 경계값 정책이 중요한 서비스(가격 구간, 리스크 등급)는 요청값, 계산 인덱스, 최종 라벨을 함께 로깅합니다.
  • 입력이 비어 있는 경우(빈 리스트) 기본 정책을 명시해 예외 대신 의도된 기본값을 반환합니다.

• 재사용 함수/구조화 팁

  • find_insert_pos, count_range, classify_by_cutoff 같은 유틸 함수를 만들어 도메인 코드와 분리합니다.
  • 팀 내에서 left/right 선택 기준을 공용 헬퍼로 캡슐화하면 경계값 사고를 크게 줄일 수 있습니다.

• 성능/메모리 체크 포인트

  • 조회가 훨씬 많고 삽입은 드문 경우 bisect + list가 매우 실용적입니다.
  • 초당 삽입이 높아 리스트 이동 비용이 커지면 구조 전환 시점(예: p95 지연 임계) 기준을 미리 정합니다.

>>> import bisect
>>> def count_range(sorted_values, lo, hi):
...     left = bisect.bisect_left(sorted_values, lo)
...     right = bisect.bisect_right(sorted_values, hi)
...     return right - left
...
>>> count_range([1, 2, 2, 4, 5, 7, 9], 2, 5)
4

위 함수는 데이터 분석, 모니터링, 알림 임계값 계산에서 그대로 재사용할 수 있는 패턴입니다. 핵심은 "조건문 분기"를 "인덱스 계산"으로 치환해 코드 길이와 버그 가능성을 동시에 줄이는 것입니다.

오늘의 결론

한 줄 요약: 정렬된 리스트를 다룰 때 위치 계산과 경계 판정은 bisect로 표준화하면 정확성과 유지보수성이 함께 올라갑니다.

기억할 것:

• bisect_left와 bisect_right는 중복 값 정책을 표현하는 도구입니다.
• insort로 삽입 시점에 정렬 상태를 자연스럽게 유지할 수 있습니다.
• 탐색은 빠르지만 삽입 비용은 별개이므로 데이터 규모를 함께 고려해야 합니다.

연습문제

1. 정렬 리스트 [5, 10, 10, 20, 30]에서 값 10이 시작되는 인덱스와 끝나는 다음 인덱스를 bisect_left/right로 구하세요.
2. cutoffs=[50, 70, 90], labels=['D','C','B','A']를 사용해 점수 [49, 50, 69, 70, 90]의 등급을 계산하고 결과를 예측하세요.
3. 실시간으로 들어오는 숫자 스트림 [7, 1, 5, 3, 9]를 insort로 삽입해 매 단계 정렬 리스트 상태를 출력하는 코드를 작성하세요.

이전 강의 정답

1. 문자열 작업 목록 FIFO 처리

>>> from collections import deque
>>> tasks = deque(['build', 'test', 'deploy'])
>>> done = []
>>> while tasks:
...     done.append(tasks.popleft())
>>> done
['build', 'test', 'deploy']

2. maxlen=5에 1~10 삽입 후 최종 상태

>>> from collections import deque
>>> d = deque(maxlen=5)
>>> for n in range(1, 11):
...     d.append(n)
>>> d
deque([6, 7, 8, 9, 10], maxlen=5)

3. 라운드로빈 7개 작업 배정

>>> from collections import deque
>>> workers = deque(['w1', 'w2', 'w3'])
>>> assigned = []
>>> for _ in range(7):
...     assigned.append(workers[0])
...     workers.rotate(-1)
>>> assigned
['w1', 'w2', 'w3', 'w1', 'w2', 'w3', 'w1']

실습 환경/재현 정보

• 실행 환경: conda env python100 (Python 3.11.14)
• 가정한 OS: macOS/Linux 공통
• 사용 모듈: bisect (표준 라이브러리)
• 실행 방법: 터미널 python REPL 또는 ipython
• 재현 체크: left/right 차이, insort 삽입 결과, 범위 개수 계산 일치 여부