[python] 이진 탐색 bisect 라이브러리

bisect를 통해 이진탐색을 쉽게 구현할 수 있고 관련 기능을 사용할 수 있다.

(그래도 이진탐색 코드 정도는 숙지하고 있도록 하자)

bisect - Array bisection algorithm - Python 3.10.5 documentation

from bisect import *

li = [1, 2, 2, 3, 3, 4]
print(bisect_left(li, 2))  # 1
print(bisect_right(li, 2))  # 3
print(bisect_left(li, 4))  # 5
print(bisect_right(li, 4))  # 6
insort(li, 2)
print(li)  # [1, 2, 2, 2, 3, 3, 4]

• bisect_left()는 찾고자 하는 값의 맨 처음 인덱스를 반환한다.
• bisect_left()는 찾고자 하는 값의 맨 마지막 인덱스 + 1 값을 반환한다.
• insort()를 통해 정렬을 해치지 않고 값을 추가할 수 있다.

---

ex) 정렬된 리스트에서 특정 값을 가지는 원소의 개수 이진 탐색으로 구하기

from bisect import *

li = [1, 2, 2, 3, 3, 4]
res = bisect_right(li, 2) - bisect_left(li, 2)
print(res)  # 2

O(logN)으로 답을 구할 수 있어 효율적이다.