개념
파이썬은 일반적인 이진탐색보다 손 쉽게 이진탐색을 사용할 수 있는 라이브러리인 bisect를 지원합니다.
물론 이진탐색을 하기 위해서는 리스트가 먼저 정렬이 되어있어야 합니다.
bisect에는 여러가지 메소드가 있지만 bisect_left(), bisect_right()메소드를 가장 많이 사용합니다.
두 메소드의 장점은 O(logN)의 시간복잡도로 동작할 수 있다는 장점이 있습니다.
bisect_left(a, x) : 리스트 a에서 x가 들어갈 가장 왼쪽 인덱스를 반환합니다.
bisect_right(a, x) : 리스트 a에서 x가 들어갈 가장 오른쪽 인덱스를 반환합니다.
| 1 | 2 | 3 | 3 | 3 | 4 | 7 |
위의 리스트를 a라고 가정했을때 bisect_left(a, 3)이면 2를 반환합니다.
위의 리스트를 a라고 가정했을때 bisect_right(a, 3)이면 5를 반환합니다.
이걸 이용해서 bisect_right값과 bisect_left값을 빼면 3 즉 원소의 개수를 파악할 수 있는 count_by_range() 함수를 정의할 수 도 있습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
|
from bisect import bisect_left, bisect_right
def count_by_range(array, left_value, right_value):
left_index = bisect_left(array, left_value)
right_index = bisect_right(array, right_value)
result = right_index - left_index
return result
array = [1, 2, 3, 3, 3, 4, 7]
print(bisect_left(array, 3)) # 3이 들어갈 가장 좌측 인덱스
print(bisect_right(array, 3)) # 3이 들어갈 가장 우측 인덱스
print(count_by_range(array, 3, 3))
|
cs |
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
| 에라토스테네스의 체를 이용한 소수 판별 (Python) (0) | 2020.12.21 |
|---|---|
| 가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python) (0) | 2020.12.19 |
| 이진탐색 (Python) (0) | 2020.12.16 |
| BFS 너비 우선탐색 (Python) (0) | 2020.12.03 |
| DFS 깊이 우선탐색 (Python) (0) | 2020.11.30 |