[Python] bisect_left, bisect_right

bisect

 

이거 없어도 괜찮을 거 같다는 고집이 있었기 때문에 따로 사용하고 있지는 않았는데, 생각보다 편리한 거 같다. 새로운 것에 대한 거부감을 줄이자.

 

bisect_left, bisect_right는 bisect 라이브러리에서 요긴하게 쓰이는 함수로, 시간복잡도는 O(logN)이라고 한다. 이 함수는 이진탐색을 통해 리스트에서 원하는 값의 인덱스를 찾아준다고 한다. 아래 코드를 통해서 이해해보자.

 

from bisect import bisect_left, bisect_right # bisect 라이브러리에서 가져온다

list = [1,1,1,1,1,2,3,4,5,6,6,6,8,9,9,9] # 반복되는 수가 있는 정렬된 리스트
list_2 = [42,5,6,8,1,57,98,4] # 무작위로 있는 리스트

print(bisect_left(list,1)) # 0, 왼쪽에 처음 나오는 위치
print(bisect_right(list,1)) # 5, 오른쪽에 처음 나오는 위치 
print(bisect_left(list_2,42)) # 5 # 왼쪽에 처음 나오는 위치, 정렬된 리스트 기준으로 알려준다.
print(sorted(list_2)) # [1, 4, 5, 6, 8, 42, 57, 98]

 

bisect_right, bisect_left는 이진탐색을 통해 찾고자 하는 값이 리스트에서 오른쪽에서 처음나오는 위치, 왼쪽에서 처음 나오는 위치를 알려준다. 특정 범위에 속하는 원소의 개수를 구하고자 할 때, count를 이용하면 효율이 떨어지는 경우에 사용하면 용이할 듯하다.

 

# bisect_left, bisect_right 함수 사용법
bisect_left(arr, value, lo, hi)
bisect_right(arr, value, lo, hi)

 

arr : 배열

value: 찾고자 하는 값

lo: 배열의 시작 범위

hi: 배열의 끝 범위

 

해당 값이 리스트에 있을 때

 

bisect_left: 해당 값이 있는 인덱스를 반환한다.

bisect_right: 해당 값이 있는 인덱스 + 1을 반환한다.

 

해당값이 리스트에 없을 때

 

bisect_left: 리스트 오름차순에 들어갈 인덱스 반환

bisect_right: 리스트 오름차순에 들어갈 인덱스 반환