bisect 이진탐색 모듈

🧩 1️⃣ 개념 정리

bisect는 정렬된 리스트(sorted list) 를 다룰 때,
특정 값이 들어갈 위치를 이진 탐색 방식(O(log N)) 으로 찾아줍니다.

💡 핵심 포인트: 리스트를 “정렬 상태로 유지한 채로” 삽입할 때 매우 유용

---

🧠 2️⃣ 기본 사용법

 

import bisect

nums = [1, 3, 4, 7, 9]
x = 5

# 삽입할 위치 찾기
pos = bisect.bisect(nums, x)
print(pos)   # 3

→ 5는 인덱스 3 위치에 들어가야 [1,3,4,5,7,9]가 정렬 상태를 유지합니다.

---

⚙️ 3️⃣ 주요 함수 4가지

함수	동작	설명
bisect_left(a, x)	왼쪽 기준 삽입 위치	동일 값이 있을 때 왼쪽으로 붙음
bisect_right(a, x) 또는 bisect(a, x)	오른쪽 기준 삽입 위치	동일 값이 있을 때 오른쪽으로 붙음
insort_left(a, x)	실제로 리스트에 삽입 (왼쪽 기준)	자동으로 정렬 유지
insort_right(a, x) 또는 insort(a, x)	실제로 리스트에 삽입 (오른쪽 기준)	자동으로 정렬 유지

---

📘 4️⃣ 예시로 이해하기

 

import bisect

arr = [10, 20, 30, 30, 40]

print(bisect.bisect_left(arr, 30))   # 2  ← 30 앞에 삽입
print(bisect.bisect_right(arr, 30))  # 4  ← 30 뒤에 삽입

bisect.insort(arr, 25)
print(arr)  # [10, 20, 25, 30, 30, 40]

 # 4 ← 30 뒤에 삽입 bisect.insort(arr, 25) print(arr) # [10, 20, 25, 30, 30, 40]

---

⏱️ 5️⃣ 시간 복잡도

• 삽입 위치 찾기 (bisect_left, bisect_right) → O(log N)
  → 이진 탐색으로 위치를 찾음
• 실제 삽입 (insort) → O(N)
  → 위치 찾기는 빠르지만, 리스트는 배열 구조라 한 칸씩 밀어야 함

---

💡 6️⃣ 실무에서 어떻게 쓰이나?

 

상황	왜 bisect 쓰는가
데이터가 항상 정렬된 상태로 유지돼야 할 때	매번 sort()보다 효율적
순위(rank), 중간값(median), 통계 백분위 계산	빠른 위치 찾기
시간/점수/가격 같은 정렬된 이벤트 스트림	새 데이터 실시간 삽입
이진 탐색 기반 조건 검사	직접 while 루프 짤 필요 없음

---

🧮 7️⃣ 예제 — 정렬된 리스트에 값 삽입

 

import bisect

scores = [10, 30, 50, 70, 90]
new_score = 65

idx = bisect.bisect_left(scores, new_score)
scores.insert(idx, new_score)
print(scores)  # [10, 30, 50, 65, 70, 90]

---

🔍 8️⃣ 예제 — 범위 내 원소 개수 구하기 (이진 탐색 응용)

예를 들어 [1,3,5,7,9,11,13] 에서 5 ≤ x ≤ 10 인 원소의 개수를 찾고 싶다면:

 

from bisect import bisect_left, bisect_right

arr = [1,3,5,7,9,11,13]
left = bisect_left(arr, 5)
right = bisect_right(arr, 10)
print(right - left)  # 3 (5,7,9)

→ O(log N) 만에 범위 개수 계산 가능 (리스트 길이에 비례하지 않음)

---

 

9️⃣ 예제 - 정렬된 리스트에서 특정 숫자가 존재하는지 여부

 

정렬된 리스트 arr에서 어떤 값 x가 존재하는지는 이렇게 판단할 수 있어요 👇

from bisect import bisect_left

# 1️⃣ 정렬된 상태의 리스트
arr = [1, 3, 4, 7, 9, 11]

# 2️⃣ x가 들어갈 위치를 이진 탐색으로 찾는다
x = 7
idx = bisect_left(arr, x)

# 3️⃣ 그 위치가 리스트 범위 안에 있고 arr[idx] == x 이면 존재
if idx < len(arr) and arr[idx] == x:
    print("✅ 존재함")
else:
    print("❌ 존재하지 않음")

 

⏱️ 시간복잡도 비교

방법	복잡도	설명
x in arr (list)	O(N)	선형탐색
bisect_left + 비교	O(log N)	이진탐색
x in set	평균 O(1)	해시 탐색 (정렬 불필요)

 

9️⃣ 요약

항목설명

모듈	import bisect
핵심 기능	정렬 리스트 내 빠른 삽입 위치 탐색
시간 복잡도	O(log N) (탐색), O(N) (삽입)
주요 함수	bisect_left, bisect_right, insort_left, insort_right
비슷한 내장 함수	list.index() (O(N), 정렬 불필요)
대표 사용 사례	실시간 정렬 유지, 순위 계산, 범위 개수 세기