파이썬 이진탐색 모듈

여태껏 파이썬에서 기본적으로 제공되는 이진탐색 함수가 없는 줄 알았는데, bisect라는 배열 이진 분할 알고리즘 모듈을 찾았습니다.

from bisect import bisect_left

위와 같은 방법으로 import 할 수 있습니다.

 

bisect_left(), bisect_right() 코드

def bisect_left(a, x, lo=0, hi=None, *, key=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(i, x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.

    A custom key function can be supplied to customize the sort order.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    # Note, the comparison uses "<" to match the
    # __lt__() logic in list.sort() and in heapq.
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo
    
    def bisect_right(a, x, lo=0, hi=None, *, key=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(i, x) will
    insert just after the rightmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.

    A custom key function can be supplied to customize the sort order.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    # Note, the comparison uses "<" to match the
    # __lt__() logic in list.sort() and in heapq.
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if x < a[mid]:
                hi = mid
            else:
                lo = mid + 1
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if x < key(a[mid]):
                hi = mid
            else:
                lo = mid + 1
    return lo

bisect_left()는 a에 x를 삽입할 위치를 찾는데, a에 x와 같은 값이 여럿 있으면 이중 가장 작은 값의 index를 반환합니다.

 

bisect_right()는 bisect_left()와 동일하나, 같은 값이 여럿 있으면 가장 큰 값의 index를 반환합니다.

 

이때 a에 x값이 없다면 해당 값이 위치해야 할 index를 반환하는데,

a = [0, 2, 4, 6], x=3이라면 index 2를 반환합니다. 즉 a.insert(2, x)로 적절한 위치에 삽입할 수 있습니다.

 

https://docs.python.org/ko/3.11/library/bisect.html

bisect — Array bisection algorithm