[python] bisect_left와 bisect_right 이해하기

bisect는 이진 탐색 알고리즘을 사용하여 목록의 정렬된 순서를 유지하게 해 주는 기능들과 관련된 모듈입니다.

그중에서도 bisect_left와 bisect_right 함수에 대해서 정리해 보도록 하겠습니다.

- bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)

기본적으로 해당 함수는 리스트 a에 x가 삽입된 후에도 a가 계속 정렬된 순서를 유지하려면 x가 어떤 인덱스 자리에 들어가야 하는지를 구하려는 의도를 가지고 있습니다.

# 6이 a에 들어가려면..
a = [1,2,4,5,7,9,10]

print(bisect.bisect_left(a,6)) # print 4

6이라는 숫자가 lst에 들어간 이후에도 lst가 정렬 상태이려면 인덱스 4 자리에 넣어주면 되겠죠. insert 함수를 사용해 확인해 보겠습니다.

a = [1,2,4,5,7,9,10]

a.insert(4,6)

print(a) # print [1,2,4,5,6,7,9,10]

따라서 정리하자면 bisect_left 함수는 정렬되어 있는 리스트 a에 x라는 값을 삽입하는 경우, x보다 더 크거나 같은 값들 중에서 가장 첫 번째에 위치한 값의 인덱스를 반환합니다.

- bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)

그런데 혼란스럽게도 bisect_left 함수 뿐 아니라 bisect_right 함수도 이 경우 동일한 인덱스 값을 반환합니다.

bisect_right 또한 정렬을 위해 x에 적합한 인덱스 값을 구한다는 동일한 의도를 가지고 있기 때문입니다. 

#6이 a에 들어가려면..
a = [1,2,4,5,7,9,10]

# right 함수를 사용해보자
print(bisect.bisect_right(a,6)) # print 4

=======

# 다시 한번
a = [21,24,26,28]

print(bisect.bisect_left(a,23)) # print 1
print(bisect.bisect_right(a,23)) # print 1

이렇게 두 함수 모두 같은 값을 반환할 거라면 굳이 왜 두 가지 함수로 나누어져 있는 걸까요? 사용하는 데 있어 차이점은 어떤 게 있을까요?

두 함수 사이의 차이점은 x 값이 리스트 a 안에 존재하는 경우로 확인해 볼 수 있습니다.

- 리스트에 x값이 존재하는 경우일 때 두  함수 비교하기

a = [1,2,3,4,5]

# lst 안에 존재하는 요소인 4를 x로 전달합니다.
print(bisect.bisect_left(a,4)) # print 3
print(bisect.bisect_right(a,4)) # print 4

두 함수의 반환 값이 달라졌습니다. 이는 이진 탐색을 하는 과정에서 어느 쪽의 중간값에 x값을 포함시킬 것인지 두 개의 함수가 반대로 처리하기 때문입니다. (상세 사항은 링크 혹은 해당 함수의 정의 선언부를 참고해 주세요.)

 

위 예시에서는 4라는 값을 전달하자 bisect_left 함수는 4의 위치인 인덱스 3, bisect_right 함수는 4의 하나 뒤(오른쪽)의 위치인 인덱스 4를 반환하고 있습니다.

즉, bisect_left는 자기 자신의 위치, bisect_right는 자기 자신의 위치에서 오른쪽으로 하나 뒤의 위치를 반환합니다.

이렇게 x값이 리스트 a 안에 존재하는 값일 경우 서로 다른 값이 나오기 때문에 두 함수를 잘 구분해서 사용해야 합니다.

- 정리

위의 케이스들을 종합해서 두가지 함수를 정리해 보자면 다음과 같습니다.

 

* bisect_left

정렬되어 있는 리스트 a에 x라는 값을 삽입하는 경우, 리스트에서 x보다 크거나 같은 가장 왼쪽 값의 인덱스를 반환합니다.

'같은' 값까지 범위에 들어가기 때문에 리스트에 x와 일치하는 값이 있을 경우 해당 값의 인덱스를 반환합니다.

 

* bisect_right

정렬되어 있는 리스트 a에 x라는 값을 삽입하는 경우, 리스트에서 x보다 큰 가장 왼쪽 값의 인덱스를 반환합니다.

더 '큰' 값만 범위에 들어가기 때문에 리스트에 x와 일치하는 값이 있다고 하더라도 해당 값보다 하나 뒤 인덱스를 반환합니다.

 

리스트에 x와 일치하는 값이 없을 경우, 동일한 x를 전달한다면 두 함수는 같은 값을 반환합니다.

---

공부하면서 스스로 이해하기 위해 정리한 글입니다.

잘못된 부분이 있다면 언제든 피드백 부탁드립니다!