🐍이진 탐색 모듈, bisect

이진탐색 개념과 구현	https://waydd.tistory.com/12
heapq	https://waydd.tistory.com/41

1. 핵심 개념

직접 구현 없이 이진 탐색과 삽입 위치 계산을 지원하는 모듈

주용도로는 정렬 리스트에서 삽입 위치 계산 과 중복을 포함한 값의 범위 탐색
→ 탐색, 삽입 위치 계산을 자동화 (특히 중복 원소 처리에 유용)
데이터를 직접 정렬하지는 않음 (정렬 유지용)
C로 구현되어 있어 속도가 빠르고 안정적

2. bisect 주요 함수

	설명	시간 복잡도
bisect.bisect_left(a, x [, lo=0, hi=len(a)])	- 정렬 리스트 a에서 x가 들어갈 가장 왼쪽 위치 반환 → 인덱스 (int) 반환	O(log N)
bisect.bisect_right(a, x [, lo=0, hi=len(a)]) or bisect.bisect(a, x [, lo=0, hi=len(a)])	- 정렬 리스트 a에서 x가 들어갈 오른쪽 다음 위치 반환 → 인덱스(int) 반환	O(log N)
bisect.insort_left(a, x [, lo=0, hi=len(a)])	- x를 왼쪽 기준으로 삽입 (정렬 유지) → 삽입 위치 찾기 + 리스트 수정	탐색 (O(log N)) + 삽입 이동 (O(N))
bisect.insort_right(a, x [, lo=0, hi=len(a)]) or bisect.insort(a, x [, lo=0, hi=len(a)])	- x를 오른쪽 기준으로 삽입 (정렬 유지) → 삽입 위치 찾기 + 리스트 수정	탐색 (O(log N)) + 삽입 이동 (O(N))

※ 매개변수
- a : 정렬된 리스트
- x : any, 탐색/삽입할 대상
- lo : 탐색 시작 인덱스
- hi : 탐색 종료 인덱스 (미포함)
→ lo, hi 로 부분 구간 탐색 가능

※ 중복 원소가 있을때 삽입 위치 탐색 동작 (bisect_*)
- bisect_left는 가장 왼쪽 인덱스를 반환
- bisect_right는 마지막 원소 다음 인덱스 반환
→ 오른쪽 기준으로 탐색한다면, 마지막 바로 뒤에 들어가야 정렬 유지됨

※ insort_* 추가 설명
- 정렬된 리스트에 값 삽입시, 정렬 상태를 유지하며 삽입하기 위해 내부적으로 bisect로 위치를 찾은 뒤 삽입 수행
- 또한 삽입 시 리스트 이동 때문에 O(N) 소요됨

3. heapq 와 비교

	bisect	heapq
자료구조	정렬된 리스트	최소 힙(Min Heap)
주요 기능	- 정렬된 리스트에 탐색/삽입 - Lower Bound / Upper Bound	- 최소값 (또는 최대값) 을 빠르게 꺼냄 - 실시간 우선순위 큐
탐색 속도	O(log N) (이진 탐색)	(O(N)) (비효율적)
삽입 속도	이진 탐색 O(log N) + 실제 삽입 O(N) (리스트 이동 비용)	O(log N)
삭제 속도	O(N) (리스트 이동 필요)	O(log N) (최솟값 pop)
정렬 상태 유지	자동 유지 (리스트 정렬 상태)	힙 규칙 유지 (부모 ≤ 자식)
정렬 후 전체 순회	바로 O(N) (이미 정렬)	정렬 상태 아님 → 전체 정렬 시 O(N log N) (heappop 반복) → 혹은 일반 정렬로 변환 후 정렬(sorted)
활용 예시	- LIS(최장 증가 부분 수열) - Lower/Upper Bound 탐색 - 정렬 유지 삽입	- 다익스트라 / A* - 최소 작업 처리 - K번째 수 문제 등

點點