[Python] bisect 활용 예시

bisect는 이진탐색(binary search)일 때 유용하게 사용 가능하다

 

이진탐색이란 간단하게 정렬되어 있는 배열내에서 특정 값을 찾아내는 것이다.

 

[1, 2, 3, 3, 3, 3, 4, 5, 6]

위와 같이 정렬된 배열이 존재할 때 3 의 갯수를 구하고 싶으면 bisect를 활용하면 된다.

def count_by_sorted_array(array, left_value, right_value):
    right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index - left_index

bisect_left(literable, value) : 왼쪽 인덱스를 구하기

bisect_right(literable, value) : 오른쪽 인덱스를 구하기

 

bisect_left 를 활용해 3이 시작하는 index 와 bisect_right 를 활용해 3 이 끝나는 지점의 index 를 구할 수 있다.