[파이썬] 이진 탐색 라이브러리 bisect

[파이썬] 이진 탐색 라이브러리 bisect

bisect

이진 탐색 알고리즘을 쉽게 구현할 수 있도록 도와주는 라이브러리.

원소들이 정렬된 리스트에서 특정 원소를 찾을 때 유용하다.

 

bisect_left(list, data) : 리스트가 정렬 상태를 유지하면서, data가 list에 몇 번 인덱스로 들어갈지를 반환(가장 왼쪽)

bisect_right(list, data) : 리스트가 정렬 상태를 유지하면서, data가 list에 몇 번 인덱스로 들어갈지를 반환(가장 오른쪽)

 

from bisect import bisect_left, bisect_right
lst = [1, 3, 4, 5]

print(bisect_left(lst, 3))
print(bisect_right(lst, 3))

1
2

 

lst는 정렬 상태이다. 이때 3을 추가로 삽입하려고 할 경우,

lst의 정렬 상태를 유지하면서 3을 넣기 위해서는 lst의 1번 인덱스에 위치한 3을 기준으로 왼쪽 또는 오른쪽을 선택할 수 있다.

 

원래 상태

lst = [1, 3, 4, 5]
0번 : 1
1번 : 3
2번 : 4
3번 : 5

bisect_left(lst, 3)의 경우  -> 1 반환

lst = [1, 3, 3, 4, 5]
0번 : 1
1번 : 3
2번 : 3
3번 : 4
4번 : 5

bisect_right(lst, 3)의 경우  -> 2 반환

lst = [1, 3, 3, 4, 5]
0번 : 1
1번 : 3
2번 : 3
3번 : 4
4번 : 5

 

그냥 코드로 이진 탐색을 구현할 경우 시간 복잡도는 O(logN)이지만, 이 두 함수를 이용할 경우 그 보다 더 빨리 계산할 수 있다는 장점이 있다.

 

 

이진 탐색으로 리스트 내의 특정 값의 개수 구하기

from bisect import bisect_left, bisect_right
lst = [1, 2, 2, 2, 3, 4, 5]

left_idx = bisect_left(lst, 2)
right_idx = bisect_right(lst, 2)

print(right_idx - left_idx)

3

left_idx = 1

right_idx = 4 가 된다.

 

이 둘의 차를 이용해 lst에서 3이 몇 개나 들어 있는지를 빠르게 구할 수 있다.