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 아니오)로 바꾸어 해결하는 기법
- 이진 탐색을 이용하여 해결
'CodingTest > 이진 탐색' 카테고리의 다른 글
정렬된 배열에서 특정 수의 개수 구하기 (0) | 2022.07.12 |
---|---|
떡볶이 떡 만들기 (0) | 2022.07.12 |
이진 탐색 알고리즘 이론 (0) | 2022.07.12 |