bisect 라이브러리를 이용한 손쉬운 이진탐색 (Python)

개념

파이썬은 일반적인 이진탐색보다 손 쉽게 이진탐색을 사용할 수 있는 라이브러리인 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() 함수를 정의할 수 도 있습니다. 

---

소스코드

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))