[파이썬] bisect

biset

정렬된 리스트에서 특정 원소를 이진 탐색해주는 라이브러리

• bisect_left(list, data) : 정렬된 리스트(list)에서, 정렬을 유지하며 data가 들어갈 가장 왼쪽 인덱스 리턴.

  위 예시에서 bisect_left(a,3)은 2를 리턴.

• bisect_right(list, data) : 정렬된 리스트(list)에서, 정렬을 유지하며 data가 들어갈 가장 오른쪽 인덱스 리턴.

  위 예시에서 bisect_right(a,3)은 4를 리턴.

---

파이썬 코드

from bisect import bisect_left, bisect_right

a = [1, 2, 3, 3, 5, 10]
x = 3

print(f"bisect_left: {bisect_left(a, x)}") # 2
print(f"bisect_right: {bisect_right(a, x)}") # 4

---

장점

• 원소들이 정렬된 리스트에서 특정 범위 내에 속하는 특정 값의 개수를 구할 때 효과적

from bisect import bisect_left, bisect_right

# [left_v, right_v] 범위 내에 있는 원소 개수 출력 함수
def cnt_within_range (arr, left_v, right_v):
    # 맨 좌측 인덱스
    left_idx = bisect_left(arr, left_v)
    # 맨 우측 인덱스
    right_idx = bisect_right(arr, right_v)
    return right_idx - left_idx

# 리스트 생성
arr = [5, 6, 7, 7, 7, 7, 8, 8, 9, 10]

# 값이 9인 원소 개수 출력
print(cnt_within_range(arr, 9, 9)) # 1
# [4, 7] 범위 내에 있는 원소 개수 출력
print(cnt_within_range(arr, 4, 7)) # 6