[파이썬] bisect 사용법

이진 탐색 알고리즘

주로 특정 원소를 찾기 위해 이진 탐색 알고리즘을 사용하곤 한다. 이는 시간 복잡도가 O(logN)이므로, 주로 사용하는 방법이곤 한다. 다음은 파이썬으로 작성한 이진 탐색 알고리즘이다.

lis = [1,2,3,4,5,6,7,8,9]

def Binary(item):
    start = 0
    end = len(lis) - 1
    while start <= end:
        mid = (start + end) // 2
        if lis[mid] == item:
            return mid
        elif lis[mid] < item:
            start = mid + 1
        else:
             end = mid - 1
    return start

이를 간단하게 bisect를 이용해 풀이 할 수 있다.

bisect_left(literable, value)
->해당 인덱스 반환
bisect_right(literable, value)
->해당 인덱스의 오른쪽 인덱스 반환

예를 들어 다음과 같이 구할 수 있다.

from bisect import bisect_left, bisect_right

nums = [0,1,2,3,4,5,6,7,8,9]
n = 5

print(bisect_left(nums, n))
print(bisect_right(nums, n))

'''
결과값
5
6
'''