[Python] Bisect

Bisect
: 정렬된 리스트에 특정 원소 삽입 후 다시 정렬할 필요가 없도록 하는 파이썬 라이브러리

• bisect_left(list, x, lo = 0, hi = len(list))
  • x가 list에 이미 있는 경우, 삽입 위치는 기존 항목 앞(왼쪽)이 된다.
  • 반환된 삽입 지점 i에 대해  →  (왼쪽) all(val < x for val in list[lo : i])  |  (오른쪽) all(val >= x for val in list[i : hi])
• bisect_right(list, x, lo = 0, hi = len(list))
• bisect(list, x, lo = 0, hi = len(list))
  • x가 list에 이미 있는 경우, 삽입 위치는 기존 항목 뒤(오른쪽)가 된다.
  • 반환된 삽입 지점 i에 대해  →  (왼쪽) all(val <= x for val in list[lo : i])  |  (오른쪽) all(val > x for val in a[i : hi])
• 예시

import bisect

a = [1, 3, 10, 20, 30]

lines = [[1, 10], [20, 60], [2, 15]]

for line in lines:
    left, right = line
    lidx = bisect.bisect_left(a, left)
    ridx = bisect.bisect_right(a, right)    # bisect.bisect(a, right)
    print(f'lidx  : {lidx}  /  ridx  : {ridx}')

# 출력값
lidx  : 0  /  ridx  : 3
lidx  : 3  /  ridx  : 5
lidx  : 1  /  ridx  : 3

 

 

---

참고

bisect - https://docs.python.org/ko/3.10/library/bisect.html