Note: bisect 라이브러리

[YimJiYoung]

bisect

bisect_left(a, x): 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
bisect_right(a, x): 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드

• 시간복잡도 : log(N)
• 참고: https://docs.python.org/ko/3/library/bisect.html

특정 범위에 속하는 원소의 개수 구하는 함수

def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index