Bisect - Python의 배열 이분법 알고리즘

긴 목록에 삽입할 때마다 정렬 작업을 수행하는 것은 프로세서가 소비하는 시간 측면에서 비용이 많이 들 수 있습니다. bisect 모듈은 삽입 후 목록이 자동으로 정렬된 상태를 유지하도록 합니다. 이를 위해 이분법 알고리즘을 사용합니다. 모듈에는 다음과 같은 기능이 있습니다.

bisect_left()

이 메서드는 정렬된 순서를 유지하기 위해 목록에서 지정된 요소에 대한 삽입 지점을 찾습니다. 목록에 이미 있는 경우 삽입 지점은 기존 항목 앞(왼쪽)에 있습니다. 반환 값은 list.insert()

양쪽_오른쪽()

이 메서드는 bisect_left()와 유사하지만 a에서 x의 기존 항목 뒤에 오는(오른쪽에 있는) 삽입 지점을 반환합니다.

bisect.insort_left()

이 메소드는 주어진 값을 정렬된 순서로 삽입합니다. 이것은 a.insert(bisect.bisect_left(a, x, lo, hi), x)

bisect.insort_right()

bisect.insort()

두 방법 모두 insort_left()와 유사하지만 동일한 값의 기존 항목 뒤에 목록에서 주어진 값을 삽입합니다.

예시

>>> 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]