[python] bisect모듈

# bisect은 이진 검색 알고리즘을 지원
# 이진 검색 알고리즘이 깔끔하게 모듈 형태로 구현되어 있음
# 정렬된 리스트 a 에 데이터 x을 삽입한다 가정
# bisect_left(a, x) 
# -> 정렬 된 순서를 유지하며 a에 x를 삽입할 때, 가장 왼쪽 인덱스 반환
# bisect_right(a, x)
# -> 정렬 된 순서를 유지하며 a에 x를 삽입할 때, 가장 오른쪽 인덱스 반환

import bisect

nums = [1,2,3,3,3,5,6,8,9]
nums.sort() #binary search는 정렬 된 배열에서 사용해야함

print(bisect.bisect_left(nums, 10)) # 9
print(bisect.bisect_right(nums, 10)) # 9

print(bisect.bisect_left(nums, 3))   # 2
print(bisect.bisect_right(nums, 3))  # 5

📕 추가

파이썬 bisect모듈의 공식 문서

#bisect.bisect_left(a, x, lo=0, hi=len(a))
#매개 변수 lo 와 hi는 고려해야 할 리스트의 부분집합을 지정하는 데 사용
#bisect.bisect_left(배열, 타겟넘버, 시작인덱스, 마지막인덱스 + 1) 라고 이해!

import bisect

nums = [-1, 0, 1, 2, 3, 4, 4, 9, 56, 90]
print(bisect.bisect_left(nums, 4))  #5출력
print(bisect.bisect_left(nums,4, 6))  #4출력