python bisect, bisect_left, bisect_right

 

Python에서 이진탐색을 라이브러리로 제공한다 ! bisect 라이브러리는 정렬된 배열 내에서 특정 원소를 찾을 때 O(logN)으로 동작한다. 

bisect_left() 함수 : 정렬된 순서를 유지하면서, 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메소드

bisect_right() 함수 : 정렬된 순서를 유지하면서, 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메소드 

중요한건 정렬된 순서를 유지! 하면서 인덱스를 찾는것이다 

예를 들어 리스트 [1, 2, 4, 4, 8]

이 있다면 bisect_left(a, 4)는 리스트에서 4가 처음으로 등장하는 위치인 2를 반환한다.

그리고 bisect_right(a, 4) 는 리스트를 4가 마지막으로 등장하는 위치 인덱스 +1 의 위치인 4를 반환한다 

이는 a[4] 위치에 넣어야지 [1, 2, 4, 4, 4, 8] 기존의 정렬된 순서를 유지할 수 있기 때문이다. 

따라서 다음 예제 코드를 이용하여 4가 등장하는 횟수를 알아낸다고 할 때 

right_index 에서 left_index를 뺀 후 1을 더하지 않아도 된다 !!

 

from bisect import bisect_left, bisect_right



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