bisect

bisect는 사전에 다음과 같이 정의 되어 있다.
 "to divide into two usually equal parts"

파이썬에서는 이분탐색을 통해 정렬된 목록에서 특정값을 삽입할 위치를 찾거나
정렬된 순서로 특정값을 삽입할 때 사용한다.

 

from bisect import *
lst =[1,3,5,5,6,8,9]

# bisect_left
# 정렬된 순서를 유지하도록 리스트에 원소를 삽입할 위치를 찾는다
pos = bisect_left(lst,2) # 2를 삽입할 인덱스는 어디인가?
print(pos) # 1

# insort_left
# 내부적으로 bisect_left로 삽입할 인덱스를 찾고 리스트의 insert 함수를 호출한다.
insort_left(lst, 2)
print(lst) # [1, 2, 3, 5, 5, 6, 8, 9]

# bisect_right
# 정렬된 순서를 유지하도록 리스트에 원소를 삽입할 위치를 찾지만
# 동일한 원소가 있다면 해당 원소의 가장 오른쪽 인덱스를 반환한다.

pos = bisect_right(lst,4) #4 를 삽입할 인덱스는 어디인가?
print(pos) # 3  (원소에 4 가 없으므로 bisect_left와 동일한 결과)

pos = bisect_right(lst,5) # 5를 삽입할 인덱스는 어디인가?
print(pos) # 5  (이미 5가 2개 있고 두번째 5의 오른쪽 인덱스를 반환)

# bisect는 bisect_right와 동의어 이다
# bisect = bisect_right

pos = bisect(lst,5) # 5를 삽입할 인덱스는 어디인가?
print(pos) # 5  (bisect_right(lst,5)와 동일)

 

 bisect 모듈로 할 수 있는 것들

. 이진 검색  : 값이 있는 지 없는 지
. 연속된 동일한 값 : 정렬된 리스트에서 bisect_left와 bisect_right를 이용하여 동일 한 값 찾기 가능
. 특정한 간격에서 값으로 매핑하기 (성적으로 ABCD 등급구하기)