bisect — 배열 이진 분할 알고리즘

소스 코드: Lib/bisect.py

이 모듈은 정렬된 리스트를 삽입 후에 다시 정렬할 필요 없도록 관리할 수 있도록 지원합니다. 값비싼 비교 연산이 포함된 항목의 긴 리스트의 경우, 이는 일반적인 방법에 비해 개선된 것입니다. 이 모듈은 기본적인 이진 분할 알고리즘을 사용하기 때문에 bisect라고 불립니다. 소스 코드는 알고리즘의 실제 예로서 가장 유용할 수 있습니다 (경계 조건은 이미 옳습니다!).

다음과 같은 함수가 제공됩니다:

bisect.bisect_left(a, x, lo=0, hi=len(a))

정렬된 순서를 유지하도록 a에 x를 삽입할 위치를 찾습니다. 매개 변수 lo 와 hi는 고려해야 할 리스트의 부분집합을 지정하는 데 사용될 수 있습니다; 기본적으로 전체 리스트가 사용됩니다. x가 a에 이미 있으면, 삽입 위치는 기존 항목 앞(왼쪽)이 됩니다. 반환 값은 a가 이미 정렬되었다고 가정할 때 list.insert()의 첫 번째 매개 변수로 사용하기에 적합합니다.

반환된 삽입 위치 i는 배열 a를 이분하여, 왼쪽은 all(val < x for val in a[lo:i]), 오른쪽은 all(val >= x for val in a[i:hi])이 되도록 만듭니다.

bisect.bisect_right(a, x, lo=0, hi=len(a))
bisect.bisect(a, x, lo=0, hi=len(a))

bisect_left()와 비슷하지만, a에 있는 x의 기존 항목 뒤(오른쪽)에 오는 삽입 위치를 반환합니다.

반환된 삽입 위치 i는 배열 a를 이분하여, 왼쪽은 all(val <= x for val in a[lo:i]), 오른쪽은 all(val > x for val in a[i:hi])이 되도록 만듭니다.

bisect.insort_left(a, x, lo=0, hi=len(a))

a에 x를 정렬된 순서로 삽입합니다. a가 이미 정렬되었다고 가정할 때 a.insert(bisect.bisect_left(a, x, lo, hi), x)와 동등합니다. O(log n) 검색이 느린 O(n) 삽입 단계에 가려짐에 유념하십시오.

bisect.insort_right(a, x, lo=0, hi=len(a))
bisect.insort(a, x, lo=0, hi=len(a))

insort_left()와 비슷하지만, a에 x를 x의 기존 항목 다음에 삽입합니다.

더 보기

bisect를 사용하여 직접적인 검색 메서드와 키 함수 지원을 포함하는 완전한 기능을 갖춘 컬렉션 클래스를 만드는 SortedCollection recipe. 검색 중에 불필요한 키 함수 호출을 피하고자 키는 미리 계산됩니다.

정렬된 리스트 검색하기

위의 bisect() 함수는 삽입 위치를 찾는 데 유용하지만, 일반적인 검색 작업에 사용하기가 까다롭거나 어색할 수 있습니다. 다음 다섯 함수는 정렬된 리스트에 대한 표준 조회로 변환하는 방법을 보여줍니다:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

다른 예제

bisect() 함수는 숫자 테이블 조회에 유용할 수 있습니다. 이 예제는 bisect()를 사용하여 (가령) 시험 점수에 대한 문자 등급을 조회하는데, 정렬된 숫자 경계점 집합에 기반합니다: 90 이상은 ‘A’, 80에서 89는 ‘B’ 등입니다:

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
...     i = bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

sorted() 함수와 달리, bisect() 함수는 key 나 reversed 인자를 갖는 것은 의미가 없는데, 비효율적인 설계 (연속적인 bisect 함수 호출이 이전의 모든 키 조회를 “기억”하지 못합니다)를 초래하기 때문입니다.

대신, 해당 레코드의 인덱스를 찾기 위해 미리 계산된 키 리스트를 검색하는 것이 좋습니다:

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # precomputed list of keys
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)