[Python] 이분탐색 bisect 라이브러리 사용법 코드

bisect 라이브러리는 파이썬에서 이진탐색을 쉽게 구현하게 해 주는 라이브러리입니다. 

알고리즘 시험에서 탐색 문제를 해결하기위해 이분탐색을 사용하는 경우가 많은데,

이분 탐색을 직접 구현하지 않고 라이브러리 만으로 수행할 수 있습니다. 

 

bisect 라이브러리

✔️ bisect_left( x, i ) : 정렬된 배열 x에서 정렬 순서를 유지한 상태로 값 i를 삽입할 가장 왼쪽 인덱스 반환   

✔️ bisect_right( x, i ) : 정렬된 배열 x에서 정렬 순서를 유지한 상태로 값 i를 삽입할 가장 오른쪽 인덱스 반환

 

예제 1

x = [1, 2, 3, 3, 3, 4, 5, 6]인 정렬된 배열이 있습니다. 

이때 배열 x에 정렬된 상태 그대로 3이라는 숫자를 삽입하는 문제를 생각해 보겠습니다. 

 

이분 탐색  ( bisect 사용 X )

nums = [1,2,3,3,3,4,5,6]
n = 3
l = 0
r = len(nums)-1
result = 0
while l <= r:
	mid = (l+r) // 2
    if nums[mid] >= n:
    	result = mid
        r = mid - 1
    else:
    	l = mid + 1
       
print(result)


## 결과값 : 2

일반적인 이분탐색을 이용하면 left 값과 right 값을 각각 시작 인덱스, 마지막 인덱스로 설정하여 mid 값을 변경하는 방식으로 구현할 수 있습니다. 이분탐색을 이용하면 O(logN)의 비용으로 탐색을 완료할 수 있습니다. 

그럼 bisect library를 쓰면 얼마나 간단히 구할 수 있는지 보겠습니다. 

 

bisect 사용 이분 탐색

from bisect import bisect_left, bisect_right

nums = [1,2,3,3,3,4,5,6]
n = 3

print(bisect_left(nums, n))  ## 결과 : 2
print(bisect_right(nums, n))  ## 결과 : 5

위 코드를 보면 bisect_left 함수는 3이 들어갈 수 있는 가장 왼쪽 인덱스를 반환합니다. 반면 bisect_right 함수는 3이 들어갈 수 있는 가장 오른쪽 인덱스를 반환합니다. 

 

 

예제 2

이번에는 정렬된 배열에서 특정 범위에 속하는 원소의 개수를 구하는 문제를 살펴보겠습니다. 

배열 x = [ 1, 2, 3, 3, 3, 4, 5, 6, 7, 7, 7, 8, 9, 10 ] 이 있을 때 3 이상 7 이하의 값을 가지는 원소의 개수를 찾겠습니다.  

from bisect import bisect_left, bisect_right

x = [1,2,3,3,3,4,5,6,7,7,7,8,9,10]

r_i = bisect_right(x, 7)
l_i = bisect_left(x, 3)
print(r_i - l_i) ## 결과 : 9

3 이상의 수를 찾기 위해 bisect_left 함수를 이용해 3이 들어갈 수 있는 가장 왼쪽 인덱스를 반환합니다. 

7 이하의 수를 찾기 위해 bisect_right 함수를 이용해 7이 들어갈 수 있는 가장 오른쪽 인덱스를 반환합니다. 

두 인덱스를 빼주면 3과 7 범위에 속하는 원소의 개수인 9가 반환됩니다.