python | 파이썬 이진 탐색 라이브러리 bisect 사용하기

bisect은 정렬된 리스트에서 특정 원소를 찾을 때 효과적으로 사용할 수 있는 라이브러리이다.

 

많은 메소드들 중 bisect_left, bisect_right를 사용하면 많은 문제들을 해결할 수 있다.

• bisect_left(a, x): 배열 a의 정렬된 상태를 유지하면서 원소 x를 삽입할 수 있는 가장 왼쪽 인덱스를 리턴
• bisect_right(a, x): 배열 a의 정렬된 상태를 유지하면서 원소 x를 삽입할 수 있는 가장 오른쪽 인덱스를 리턴

from bisect import bisect_left, bisect_right

 

정렬된 배열 array=[1, 2, 3, 4, 4, 6, 8, 9]가 있을 때, 4를 삽입할 수 있는 가장 왼쪽 인덱스와 가장 오른쪽 인덱스를 찾기 위해서는 다음과 같이 코드를 작성할 수 있다.

from bisect import bisect_left, bisect_right

array = [1, 2, 3, 4, 4, 6, 8, 9]
x = 4

print(bisect_left(array, x)) # 3
print(bisect_right(array, x)) # 5

array의 정렬을 유지하면서 x=4를 삽입할 수 있는 가장 왼쪽 위치는 [1, 2, 3, (4), 4, 4, 6, 8, 9]가 될 것이고, 이때의 인덱스는 3이므로 bisect_left의 결과로 3이 리턴된다.

array의 정렬을 유지하면서 x=4를 삽입할 수 있는 가장 오른쪽 위치는 [1, 2, 3, 4, 4, (4), 6, 8, 9]가 될 것이고, 이때의 인덱스는 3이므로 bisect_right의 결과로 5가 리턴된다.

 

bisect_left와 bisect_right를 사용해 해당 배열에서 특정 범위에 포함되는 원소의 개수를 구할 수 있다.

from bisect import bisect_left, bisect_right

# 값이 [left, right] 범위에 있는 데이터의 개수를 반환하는 함수
def count_by_range(a, left, right):
    right_index = bisect_right(a, right)
    left_index = bisect_left(a, left)
    return right_index - left_index

array = [1, 2, 3, 4, 4, 6, 8, 9]

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

count_by_range 함수는 배열 a와 left, right를 매개변수로 넘겨받는다.

배열 a에서 bisect_right을 사용하여 right를 삽입할 수 있는 가장 오른쪽 인덱스를 찾아 right_index에 저장하고

bisect_left를 사용하여 left를 삽입할 수 있는 가장 왼쪽 인덱스를 찾아 left_index에 저장한다.

right_index에서 left_index를 빼면 left에서 right 간의 인덱스 차를 구할 수 있고, 그 인덱스 차는 left에서 right 사이에 포함된 값의 개수를 의미한다.

즉, right_index - left_index는 left에서 right까지의 범위에 포함되는 데이터의 개수가 되는 것이다.

이 코드를 실행하면, [-1, 3] 범위에 있는 데이터인 개수인 3이 출력된다.(1, 2, 3)

 

위 count_by_range 함수를 이용하면 배열 a에서 원소 x의 개수를 구할 수도 있다.

from bisect import bisect_left, bisect_right

# 값이 [left, right] 범위에 있는 데이터의 개수를 반환하는 함수
def count_by_range(a, left, right):
    right_index = bisect_right(a, right)
    left_index = bisect_left(a, left)
    return right_index - left_index

array = [1, 2, 3, 4, 4, 6, 8, 9]

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

count_by_value 함수를 사용하면 left에서 right 범위에 해당하는 원소의 개수를 구할 수 있으므로, left와 right에 같은 값을 입력해 주면 해당 값의 개수를 구할 수 있다.

이 코드는 [4, 4] 범위에 해당하는 데이터의 개수를 구하는 것이므로 array에서 [4, 4]에 해당하는 4의 개수인 2를 출력한다.