Bisect Module

Bisect

 

python에서 제공하는 패키지

이진 탐색을 쉽게 할 수 있도록 하는 함수

 

배열에서 특정 값을 찾는 방법은

 

1) for문을 앞에서부터 돌린다.

2) left, right를 둬서 이분 탐색을 한다. 

 

bisect는 2)번을 좀 더 쉽게 할 수 있도록 만들어 놓은 함수이다. 

 

예를 들어서 점수에 따른 등급을 찾는다고 해보자

arr = [60, 70, 80, 90]
val = ['F', 'D', 'C', 'B', 'A']

print(bisect.bisect_left(arr, 89),bisect.bisect_right(arr, 89), val[bisect.bisect_right(arr, 89)])
# 3 3 B
print(bisect.bisect_left(arr, 79), bisect.bisect_right(arr, 79), val[bisect.bisect_right(arr, 79)])
# 2 2 C

 

주의할 점

bisect_left는 값을 포함해서 계산하고, bisect_right는 그 다음 위치를 넘겨준다

무슨말이고 하니

def countRange(nums, left, right):
    r = bisect.bisect_right(nums, right)
    l = bisect.bisect_left(nums, left)

    print(l, r) # 2, 6
    return r - l

nums = [1,2,3,4,5,6,7,8,9,10] # 3~6까지 갯수 구하기
print(countRange(nums, 3, 6))

위의 예제를 보면 bisect_right는 6이 나오고, bisect_left는 2가 나온다. 

nums에서 3을 찾으면 index가 2이고, bisect_left는 2를 포함해서 결과값이 나온다

반면, nums에서 6을 찾으면, index가 5이지만 bisect_right는 한칸 뒤인 6을 넘겨준다.