Bisect란?

파이썬에서 Binary Search를 편하게 하라고 만든 모듈이다.

bisect를 쓰면 특정값이 어디에 들어갈지 쉽게 알 수 있다.

예제

import bisect

arr = [100, 200, 300]
print(bisect.bisect_left(arr, 0)) # 0
print(bisect.bisect_left(arr, 150)) # 1
print(bisect.bisect_left(arr, 200)) # 1
print(bisect.bisect_left(arr, 250)) # 2
print(bisect.bisect_left(arr, 300)) # 2
print(bisect.bisect_left(arr, 350)) # 3

어떤 값(0, 150, 200 …)이 정렬된 배열(arr)에 들어간다 쳤을때, 그 인덱스를 알려준다.
bisect_left는 위치를 찾으려는 값(200)이 배열에 이미 있다면(200) 그 있는놈의 왼쪽에 둔다는 말이다. 그래서, 위의 예제에서도 bisect.bisect_left(arr, 200)이 3이 아닌 1을 리턴한다.

import bisect

arr = [100, 200, 300, 400, 500, 600]
print(bisect.bisect_left(arr, 0)) # 0
print(bisect.bisect_left(arr, 150, 2, 5)) # 2
print(bisect.bisect_left(arr, 450, 3, 5)) # 4

bisect_left는 범위도 지정할 수 있다.
150을 arr[2 ~ 5] 사이에 넣어야 하니까, 맨 왼쪽인 2가 된다.
450을 arr[3 ~ 5] 사이에 넣어야 하니까, 400보다 크기때문에, 4가 된다.