[Python] 이진 탐색을 위한 bisect 모듈 사용법

1. bisect 모듈이란?

• 이진 탐색을 쉽게 구현하도록 돕는 모듈
• 더 정확하게는 정렬된 list에 element를 삽입할 때, list가 정렬된 순서를 유지하도록 한다.

제공되는 함수

1. .bisect_left(a, x, lo=0, hi=len(a), *, key=None)
   • a의 정렬을 유지한 채 x를 삽입할 수 있는 위치들 중 가장 왼쪽을 반환
2. .bisect(a, x, lo=0, hi=len(a), *, key=None)
   • a의 정렬을 유지한 채 x를 삽입할 수 있는 위치들 중 가장 오른쪽을 반환
   • .bisect_right와 동일
3. .insort_left(a, x, lo=0, hi=len(a), *, key=None)
   • bisect_left 위치에 값을 삽입
4. .insort(a, x, lo=0, hi=len(a), *, key=None)
   • bisect_right 위치에 값을 삽입
   • .insort_right와 동일

지정 가능한 인자

• a : 정렬된 list
• x : a에 삽입할 element
• lo, hi: a의 일부 구간에 대해서만 삽입 위치를 찾고 싶을 때 사용
  (기본값: lo=0, hi=len(a))
• Key: 각 요소를 비교하기 전에 변환하는 함수
  (기본값: Key=None → list 요소를 직접 비교)

2. 예제로 이해하기

import bisect

lst = [4, 4, 2, 5, 1, 10, 7, 7] # 탐색할 list는 항상 오름차순으로 정렬되어 있어야 함에 유의하자!
lst = sorted(lst)  # 정렬 후: lst = [1, 2, 4, 4, 5, 7, 7, 10]

# 3을 삽입할 왼쪽 위치 찾기
pos_left = bisect.bisect_left(lst, 3)
print("bisect_left:", pos_left)  # bisect_left: 2 (1, 2와 4 사이에 삽입 -> index=2)

# 5을 삽입할 오른쪽 위치 찾기
pos_right = bisect.bisect_right(lst, 5)
print("bisect_right:", pos_right)  # bisect_right: 5 (1, 2, 4, 4, 5와 7 사이에 삽입 -> index=5)

# bisect는 bisect_right와 동일하다.
pos = bisect.bisect(lst, 5)
print("bisect:", pos)  # bisect: 5

# 3을 bisect_left 위치에 삽입하
bisect.insort_left(lst, 3)
print("insort_left:", lst)  # insort_left: [1, 2, 3, 4, 4, 5, 7, 7, 10]

# 5을 bisect_right 위치에 삽입
bisect.insort_right(lst, 5)
print("insort_right:", lst)  # insort_right: [1, 2, 3, 4, 4, 5, 5, 7, 7, 10]

3. 문제 풀어보기

이해를 위해 아래 두 문제를 bisect 를 이용해 풀어봅시다.

• https://www.acmicpc.net/problem/1920
• https://www.acmicpc.net/problem/10816

정답 예시:

• https://velog.io/@beaver_zip/1920-수-찾기-Python
• https://velog.io/@beaver_zip/10816-숫자-카드-2-Python

---

참고 자료

• https://docs.python.org/3/library/bisect.html