Python bisect 모듈 완벽 가이드 – 이분 탐색으로 정렬된 리스트 유지하기

긴 리스트에 요소를 삽입할 때마다 매번 정렬 연산을 수행하면 프로세서 시간이 크게 낭비될 수 있습니다. 파이썬의 bisect 모듈은 이분법(bisection) 알고리즘을 활용하여, 삽입 작업 후에도 리스트가 자동으로 정렬된 상태를 유지하도록 도와줍니다. 이 모듈이 제공하는 주요 함수는 다음과 같습니다.

bisect_left()

정렬 순서를 유지하면서 주어진 요소를 삽입할 수 있는 위치를 찾아 반환합니다. 만약 동일한 값이 리스트에 이미 존재한다면, 기존 항목들보다 앞쪽(왼쪽)에 해당하는 삽입 위치를 반환합니다. 반환된 값은 list.insert()의 첫 번째 인수로 그대로 사용할 수 있습니다.

bisect_right()

bisect_left()와 유사하게 동작하지만, 동일한 값이 이미 존재하는 경우 기존 항목들보다 뒤쪽(오른쪽)에 해당하는 삽입 위치를 반환한다는 점이 다릅니다.

bisect.insort_left()

주어진 값을 정렬 순서를 유지하면서 리스트에 직접 삽입합니다. 내부적으로 a.insert(bisect.bisect_left(a, x, lo, hi), x)와 동일한 방식으로 동작합니다.

bisect.insort_right(), bisect.insort()

두 메서드 모두 insort_left()와 비슷하지만, 동일한 값의 기존 항목들이 있으면 그 뒤에 새 값을 삽입합니다. 참고로 insort()는 insort_right()의 별칭(alias)입니다.

이분 탐색 기반으로 삽입 위치를 찾기 때문에 위치 탐색은 O(log n)의 시간 복잡도로 매우 빠르게 수행되며, 대량의 데이터를 다룰 때 특히 유용합니다.

사용 예제

>>> nums = [45,21,34,87,56,12,5,98,30,63]
>>> nums.sort()
>>> nums
[5, 12, 21, 30, 34, 45, 56, 63, 87, 98]
>>> import bisect
>>> p = bisect.bisect_left(nums,50)
>>> p
6
>>> nums.insert(p,50)
>>> nums
[5, 12, 21, 30, 34, 45, 50, 56, 63, 87, 98]
>>> bisect.insort(nums, 29)
>>> nums
[5, 12, 21, 29, 30, 34, 45, 50, 56, 63, 87, 98]

위 예제에서 bisect_left(nums, 50)는 값 50이 들어갈 인덱스 6을 반환하고, 이를 이용해 리스트에 삽입한 결과 정렬 상태가 그대로 유지됩니다. 또한 insort()를 사용하면 삽입 위치를 일일이 계산할 필요 없이 한 번의 호출로 정렬된 상태를 유지하며 값을 추가할 수 있습니다.