[Python] 이진 탐색 라이브러리 bisect

알고리즘 문제를 풀다 보면 이진 탐색을 사용해야할 때가 많다.

다른 언어에서는 다음과 같이 직접 반복문을 만들어, 이진 탐색 알고리즘을 구현한다

def bisect(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

mylist = [1, 2, 3, 7, 9, 11, 33]
print(bisect(mylist, 3))

 

파이썬에서는 bisect.bisect 메소드를 사용하면 훨씬 간단하게 코드를 짤 수 있다.

 

biset_left(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환 ( C++의 lower_bound와 동일)

bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환 (C++의 upper_bound와 동일)

 

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x)) # 2
print(bisect_right(a, x)) # 4

값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
	right_index = bisect_right(a, right_value)
    right_index = bisect_left(a, left_value)
    return right_index - left_index
    
# 배열 선언
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a, 4, 4)) # 2

# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(1, -1, 3)) # 6

 

참고: 파이썬을 파이썬 답게: https://programmers.co.kr/learn/courses/4008,
이것을 취업을 위한 코딩 테스트다 with 파이썬: https://www.youtube.com/watch?v=-Gx0T92-7h8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=26