파이썬(Python) bisect 사용법 정리

bisect 라이브러리는 정렬된 리스트에서 특정 값의 위치를 찾거나, 새로운 값을 삽입할 위치를 찾는 등 이진 탐색(binary search)을 수행하는데 사용됩니다. 이진 탐색은 리스트의 길이가 N일 때 O(logN)의 시간 복잡도를 갖기 때문에 대규모 데이터 처리에서 유용하게 사용됩니다.

bisect 라이브러리에는 다음과 같은 함수들이 있습니다.

1. bisect_left(a, x, lo=0, hi=len(a))

리스트 a에 x를 삽입할 위치를 반환합니다. 만약 리스트 a 내에 x가 이미 존재하는 경우, x의 가장 왼쪽 위치를 반환합니다.

a : 탐색 대상이 되는 정렬된 리스트
x : 찾고자 하는 값
lo : 탐색 시작 위치(기본값은 0)
hi : 탐색 종료 위치(기본값은 len(a))

import bisect

a = [1, 2, 4, 4, 6]
print(bisect.bisect_left(a, 4))  # 2
print(bisect.bisect_left(a, 3))  # 2

2. bisect_right(a, x, lo=0, hi=len(a))

리스트 a에 x를 삽입할 위치를 반환합니다. 만약 리스트 a 내에 x가 이미 존재하는 경우, x의 가장 오른쪽 위치 다음 인덱스를 반환합니다.

a : 탐색 대상이 되는 정렬된 리스트
x : 찾고자 하는 값
lo : 탐색 시작 위치(기본값은 0)
hi : 탐색 종료 위치(기본값은 len(a))

import bisect

a = [1, 2, 4, 4, 6]
print(bisect.bisect_right(a, 4))  # 4

3. bisect(a, x, lo=0, hi=len(a))

bisect_right() 함수와 동일합니다.

a : 탐색 대상이 되는 정렬된 리스트
x : 찾고자 하는 값
lo : 탐색 시작 위치(기본값은 0)
hi : 탐색 종료 위치(기본값은 len(a))

import bisect

a = [1, 2, 4, 4, 6]
print(bisect.bisect(a, 4))  # 4

4. insort_right(a, x, lo=0, hi=len(a))

리스트 a에 x를 삽입합니다. 리스트 a가 이미 정렬되어 있다고 가정합니다. 만약 리스트 a 내에 x가 이미 존재하는 경우, x를 리스트 a 내에서 가장 오른쪽 위치 다음 인덱스에 삽입합니다.

a : 삽입 대상이 되는 정렬된 리스트
x : 삽입할 값
lo : 삽입 시작 위치(기본값은 0)
hi : 삽입 종료 위치(기본값은 len(a))

import bisect

a = [1, 2, 4, 6]
bisect.insort_right(a, 3)
print(a)  # [1, 2, 3, 4, 6]

5. insort()

insort_right() 함수와 동일합니다.

a : 삽입 대상이 되는 정렬된 리스트
x : 삽입할 값
lo : 삽입 시작 위치(기본값은 0)
hi : 삽입 종료 위치(기본값은 len(a))

import bisect

a = [1, 2, 4, 6]
bisect.insort(a, 3)
print(a)  # [1, 2, 3, 4, 6]

위의 예제 코드를 보면 bisect 라이브러리를 이용해 정렬된 리스트에서 값을 찾거나 삽입하는 방법을 알 수 있습니다. 이러한 함수들을 이용하면 리스트 내에서 값을 찾거나 추가할 때 일반적인 반복문으로 구현하는 것보다 더 효율적이고 간단하게 구현할 수 있습니다.