python docs에 의하면 bisect를 다음과 같이 설명하고 있다.
이 모듈은 정렬된 리스트를 삽입 후에 다시 정렬할 필요 없도록 관리할 수 있도록 지원합니다. 값비싼 비교 연산이 포함된 항목의 긴 리스트의 경우, 이는 일반적인 방법에 비해 개선된 것입니다. 이 모듈은 기본적인 이진 분할 알고리즘을 사용하기 때문에 bisect라고 불립니다. 소스 코드는 알고리즘의 실제 예로서 가장 유용할 수 있습니다
즉, 어떤 정렬된 리스트를 탐색할때 일반적인 반복문으로 구현한다면, O(n)의 시간복잡도가 걸리겠지만 bisect는 이분 탐색을 이용해 리스트를 탐색하므로 O(logN)의 시간복잡도를 가지기 때문에 보다 효율적인 탐색이 가능하다.
bisect 모듈이 제공하는 주요 함수들은 다음과 같다. 아래 함수들의 기본 탐색 범위는 내부적으로 시작점(lo)과 끝(hi)으로 잡는 값을 각각 0과 ,len(a)로 사용한다.
-
bisect_left(a, x, lo=0, hi=len(a))
정렬된 리스트 a에서 원소 x가 들어갈 적절한 위치를 찾아 반환한다. 만약 x가 이미 리스트에 있을 경우, x가 들어갈 수 있는 가장 왼쪽 위치를 반환한다. -
bisect_right(a, x, lo=0, hi=len(a))
정렬된 리스트 a에서 원소 x가 들어갈 적절한 위치를 찾아 반환한다. 만약 x가 이미 리스트에 있을 경우, x가 들어갈 수 있는 가장 오른쪽 위치를 반환한다.
-
insort_left(a, x, lo=0, hi=len(a))
정렬된 리스트 a에서 x가 들어갈 적절한 위치에 직접 삽입한다. 만약 x가 이미 리스트에 있을 경우, x가 들어갈 수 있는 가장 왼쪽 위치에 삽입한다.
-
insort_right(a, x, lo=0, hi=len(a))
정렬된 리스트 a에서 x가 들어갈 적절한 위치에 직접 삽입한다. 만약 x가 이미 리스트에 있을 경우, x가 들어갈 수 있는 가장 오른쪽 위치에 삽입한다.
이를 이용하면 특정 값을 갖는 원소의 개수를 세는 문제 등을 보다 쉽고 빠르게 풀어낼 수 있다.
