값이 특정 범위에 속하는 데이터 개수 구하기

1. 새로 알게된 것 (파이썬 이진 탐색 라이브러리)

• bisect_left(a, x)
  • 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
• bisect_right(a, x)
  • 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

• a라는 배열에 4가 있는 인덱스의 바로 왼쪽
• a라는 배열에 4가 있는 인덱스의 바로 오른쪽

from bisect import bisect_left, bisect_right

a = [1,2,4,4,8]
x = 4

print(bisect_left(a,x))
print(bisect_right(a,x))

#출력 결과
2
4

---

2. 값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_balue]인 데이터의 개수를 반환하는 함수
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

#배열 선언
a = [1,2,3,3,3,3,4,4,8,9]

#값이 4인 데이터 개수 출력
print(count_by_range(a,4,4))

#값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(a,-1, 3))

#출력 결과
2
6

---

3. 파라메트릭 서치(Parametric Search)

• 최적화 문제를 결정 문제(예 or 아니오)로 바꾸어 해결하는 기법
• 이진 탐색을 이용하여 해결