[파이썬] bisect 라이브러리

bisect 라이브러리를 이용하면 이진 탐색을 쉽게 구현할 수 있다.

bisect 라이브러리는 정렬된 배열에서 특정 원소를 찾을 때 매우 효과적이다.

 

bisect 내부 함수

• bisect_left(a,x) : 리스트 a에서 데이터 x를 삽입할 가장 왼쪽 인덱스를 리턴한다.
• bisect_right(a,x) : 리스트 a에서 데이터 x를 삽입할 가장 오른쪽 인덱스를 리턴한다.
• 이 두 함수는 시간 복잡도 O(logN)으로 동작한다.

사용 예:

from bisect import bisect_left, bisect_right

a = [1,2,4,4,8]
x = 4
print(bisect_left(a,x), bisect_right(a,x)) # 2 4