[Python] bisect 라이브러리 (lower bound, upper bound)

bisect 라이브러리에 있는 bisect_left, bisect_right에 대해 공부하려 합니다.

1. bisect?

- 정렬된 리스트에서 이진 탐색을 이용해 데이터를 찾는 메서드를 제공

- O(logN)의 시간 복잡도로 데이터를 찾을 수 있다

- bisect_left는 lower bound로, bisect_right는 upper_bound로 사용할 수 있다

 

2. lower bound와 upper bound

bisect 라이브러리에서 제공하는 메서드는 이진 탐색과 완전히 일치하지는 않고 조금 차이점이 있다.

위에서 말한 것처럼 bisect_left는 lower bound 알고리즘을, bisect_right는 upper bound 알고리즘을 수행한다.

 

- binary search: 찾고자 하는 값이 존재하는 경우에만 위치를 반환함

- lower bound: 찾고자 하는 값 이상이 처음 나타나는 위치를 반환함

- upper bound: 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치를 반환함

 

1) target이 리스트에 존재하는 경우

binary search와 다르게 lower bound와 upper bound는 찾고자 하는 값이 없어도 그 값보다 큰 위치를 반환한다.

또 같은 값이 여러 개여도 처음 위치나 마지막 위치만 반환하면 되므로 같은 값이 중복되어도 된다.

from bisect import bisect_left
from bisect import bisect_right

target = 20
nums = [10, 20, 20, 20, 20, 30, 40, 50, 60]
print('bisect_left: ', bisect_left(nums, target))
print('bisect_right: ', bisect_right(nums, target))

bisect_left: target인 20이 처음 나온 위치는 1이다.

bisect_right: target인 20보다 큰 인덱스가 처음 나온 위치는 5이다.

 

2) target이 리스트에 존재하지 않는 경우

target = 11
nums = [10, 20, 20, 20, 20, 30, 40, 50, 60]
print('bisect_left: ', bisect_left(nums, target))
print('bisect_right: ', bisect_right(nums, target))

bisect_left: target인 11 이상인 값이 처음 나오는 위치는 1이다.

bisect_right: target인 11보다 큰 값이 처음 나오는 위치는 1이다.

- 이상인지 초과인지만 판단하면 사용할 때 헷갈리지 않고 사용할 수 있다.

 

3. lower bound를 이용한 이진 탐색 구현

이진 탐색은 찾고자 하는 값 target이 있는 경우 target의 인덱스를 반환한다.

중복된 값은 없다고 가정한다.

찾고자 하는 값의 위치를 알아야 하므로 target보다 큰 위치를 반환하는 upper bound보다는 lower bound를 사용하는 것이 편하다.

from bisect import bisect_left

def binarysearch(nums, target):
    idx = bisect_left(nums, target)
    if idx < len(nums) and nums[idx] == target:
        return idx
    return -1

bisect_left를 이용해 target 이상인 값이 처음 나오는 위치를 idx에 저장한다.

idx의 크기가 nums의 len보다 커지는 경우 또는 target이 nums에 존재하지 않는 경우 없다고 간주하고 -1을 반환한다.