🐧 이진 탐색 (bisect)

bisect 모듈의 아래 함수들을 쓰면 정렬된 배열에 대해서 이진 탐색으로 인덱스를 찾아줌

bisect_left

• 삽입할 위치의 왼쪽 인덱스 리턴
• 해당하는 값이 있을 경우 해당 인덱스 리턴

bisect_right (= bisect)

• 삽입할 위치의 오른쪽 인덱스 리턴
• 해당하는 값이 있을 경우 해당 인덱스 + 1 리턴

import bisect

a = [1, 3, 5, 7, 9]
print(bisect.bisect_left(a, 3)) # 1
print(bisect.bisect_right(a, 3)) # 2

# 해당하는 값이 없을 때는 둘 다 동일한 동작을 함
print(bisect.bisect_left(a, 4)) # 2
print(bisect.bisect_right(a, 4)) # 2

insort_left

• 정렬유지하면서 삽입
• 같은 값의 왼쪽에 (즉 같은값이 있으면 그자리에 밀어내면서 들어감)

insort_right

• 같은 값의 오른쪽에