[Python] bisect - 배열 이진 분할 알고리즘

bisect 모듈

• 기본적인 이진 분할 알고리즘을 사용하기 때문에 bisect이라고 부른다.

 

메소드

bisect_left(a, x, lo=0, hi=len(a), *, key=None)

• 정렬된 순서를 유지하기 위해 a에 x를 삽입할 위치를 찾는다.
• lo와 hi는 고려해야 할 리스트의 부분 집합을 지정하는 데 사용될 수 있다. 
• x가 a에 이미 있으면 삽입 위치는 기존 항목 앞(왼쪽)이 된다.

 

bisect_right(a, x, lo=0, hi=len(a), *, key=None)

bisect(a, x, lo=0, hi=len(a), *, key=None)

• bisect_left()와 비슷하게 x가 a에 이미 있으면 삽입 위치는 기존 항목 뒤(오른쪽)이 된다.

 

예제

from bisect import bisect_left, bisect_right

lst = [1, 1, 2, 3, 3, 3, 4, 4]

index = bisect_left(lst, 100)
print(index) #출력 : 8

index = bisect_right(lst, 1)
print(index) #출력 : 2

• bisect_left()와 bisect_right()는 리스트에 삽입할 위치를 찾아준다.

 

index = bisect_left(lst, 100)
print(index) #출력 : 8

• 리스트의 길이는 8이며 100을 리스트에 넣는다면 인덱스 8에 넣을 수 있다.

 

index = bisect_right(lst, 1)
print(index) #출력 : 2

• 리스트에 1을 넣으려면 오른쪽을 기준으로 인덱스 2에 넣을 수 있다. 

 

bisect_left()와 bisect_right()를 이용해서 리스트에 어떤 값이 몇 개가 있는지 계산할 수 있다.

from bisect import bisect_left, bisect_right

lst = [1, 1, 2, 3, 3, 3, 4, 4]

index = bisect_left(lst, 3)
print(index) # 출력: 3

index = bisect_right(lst, 3)
print(index) # 출력 : 6

result = bisect_right(lst, 3) - bisect_left(lst, 3)
print(result) # 출력 : 3

• bisect_left()를 통해 3을 인덱스 3에, bisect_right()를 통해 인덱스 6에 넣을 수 있다는 것을 알 수 있다. 그 말은 인덱스 3부터 5에 3이 있다는 뜻이다.
• bisect_right(lst, 3) - bisect_left(lst, 3)은 3이며 lst 안에 3이 3개 있다. 

---

회고

• 처음에 bisect 모듈이 찾고자 하는 값에 대해 리스트의 왼쪽, 오른쪽 인덱스를 반환하는 것으로 착각했었다.

---

Ref.

1. bisect 모듈 관련 공식 문서 / https://docs.python.org/ko/3/library/bisect.html

---

* 잘못된 부분에 대해 댓글 남겨주시면 감사하겠습니다! 😀