bisect_left는 같은 값이 이미 있으면 그 값들 앞의 삽입 지점을, bisect_right는 뒤의 삽입 지점을 돌려줍니다. 중복 구간은 두 위치의 반열린 범위 [left, right)입니다.
두 함수는 특정 값이 존재하는지 판정하는 검색 함수가 아닙니다. 입력은 정렬되어 있어야 하며, 없을 때도 질서가 유지될 삽입 지점을 반환합니다.
bisect는 찾은 값이 아니라 삽입 위치를 줍니다
bisect를 일반적인 검색 함수처럼 생각하면 중복 원소가 있는 문제에서 인덱스를 잘못 읽기 쉽습니다. Python 3.12 문서는 bisect 모듈이 정렬된 배열의 삽입 지점을 찾고, 특정 원소를 발견했는지 확인하기 위한 함수는 아니라고 설명합니다. 입력 목록은 찾는 값과 같은 정렬 기준으로 이미 정렬되어 있어야 합니다. 함수는 ==로 일치 항목을 골라내지 않고 순서를 유지할 경계를 계산합니다. 따라서 반환값은 값 자체의 위치가 아니라 새 값을 삽입해도 순서가 유지될 경계입니다.
왼쪽과 오른쪽 경계로 중복 세 개를 자릅니다
점수 목록 [1, 5, 5, 5, 9]에서 값 5의 첫 위치와 마지막 다음 위치를 알고 싶다고 하겠습니다. bisect_left는 기존 5들 앞인 인덱스 1을 반환합니다. bisect_right는 기존 5들 뒤인 인덱스 4를 반환합니다. 파이썬의 슬라이스 끝은 포함하지 않으므로 scores[left:right]는 [5, 5, 5]가 됩니다. 개수는 오른쪽 경계에서 왼쪽 경계를 빼면 3입니다.
from bisect import bisect_left, bisect_right
scores = [1, 5, 5, 5, 9]
left = bisect_left(scores, 5)
right = bisect_right(scores, 5)
print(left, right)
print(scores[left:right])
print(right - left)| 함수 | 반환값 | 경계의 의미 |
|---|---|---|
| bisect_left(scores, 5) | 1 | 5보다 작은 항목 뒤, 동등값 구간 앞 |
| bisect_right(scores, 5) | 4 | 동등값 구간 뒤, 5보다 큰 항목 앞 |
| right - left | 3 | 값 5의 개수 |
두 위치를 이용하면 값이 있는 연속 구간을 바로 잘라낼 수 있고, 정렬된 값에서 특정 기준 이하·이상인 원소 수를 계산하는 데도 활용할 수 있습니다. 예를 들어 bisect_left(scores, 5)는 5보다 작은 값의 개수와 같습니다. bisect_right(scores, 5)는 5 이하 값의 개수입니다. 이 관계는 Python 문서의 분할 조건과 맞닿아 있습니다. 왼쪽 경계의 앞쪽에는 찾는 값보다 작은 요소만 있고, 오른쪽 경계의 앞쪽에는 찾는 값 이하 요소만 있습니다.
범위가 비어 있는 경우까지 같은 식으로 처리합니다
- 목록이 대상 값과 같은 기준으로 오름차순 정렬되어 있는지 확인합니다.
left = bisect_left(items, target)을 계산합니다.right = bisect_right(items, target)을 계산합니다.items[left:right]로 동등값 구간을 얻고right - left로 개수를 구합니다.- 검색 존재 여부가 필요하면 경계가 목록 안인지 확인한 뒤
items[left] == target을 따로 비교합니다.
찾는 값이 목록에 없을 때도 예외는 아닙니다. 예를 들어 [1, 5, 5, 5, 9]에서 7을 찾으면 두 함수는 9 앞의 삽입 위치를 반환해 빈 슬라이스가 됩니다. 존재 여부를 확인하려면 left < len(items)인지 먼저 확인하고 그 위치의 값과 target을 비교해야 합니다. 대상이 목록 끝보다 큰 경우 left가 길이와 같을 수 있으므로, 범위 확인 없이 items[left]에 접근하면 IndexError가 납니다.
정렬 전제와 오른쪽 경계의 배타성을 놓치지 않습니다
가장 흔한 실수는 정렬하지 않은 목록에 bisect를 적용하고 결과가 일반 검색처럼 맞을 것이라고 기대하는 것입니다. 이진 탐색은 비교 결과로 검색 범위를 줄이므로, 목록의 정렬이 깨져 있으면 반환 위치가 해당 값을 포함하는 구간이 되리라는 보장이 없습니다. 목록을 정렬한 뒤 원래 순서의 인덱스가 필요하다면 정렬 전후의 관계도 별도로 보존해야 합니다. 또 right는 마지막 일치 인덱스가 아니라 동등값 구간 바로 다음 위치입니다. 따라서 마지막 인덱스가 필요하면 구간이 비지 않았을 때 right - 1이 됩니다.
정렬 목록: [1, 5, 5, 5, 9]
left = 1, right = 4
동등값 구간: [left, right) = 인덱스 1, 2, 3
개수: right - left = 3
마지막 인덱스: right - 1 = 3bisect의 기본 함수는 오름차순 비교를 전제로 합니다. 내림차순 목록에 같은 호출을 그대로 적용하거나, 정렬 시 사용한 키와 탐색 시의 비교 기준을 다르게 두면 경계가 의도와 달라집니다. 레코드 목록에서는 key 인자를 활용할 수 있지만, Python 3.12 문서가 설명하듯 key 함수는 목록의 요소에 적용되고 찾는 x 값에는 적용되지 않습니다. 복합 레코드 탐색이라면 이 비대칭도 함께 확인하세요.
정답을 가리고 확인해 보세요
이 글을 위해 만든 학습 예시이며 공식 기출문제나 판매 카드의 인용이 아닙니다.
정렬된 [2, 4, 4, 4, 8]에서 값 4의 동등값 구간을 슬라이스로 얻으려면 어떤 두 경계를 쓰며 결과 개수는 얼마인가요?
정답과 해설 확인
bisect_left는 1, bisect_right는 4를 반환하므로[1:4]가 구간이며 개수는 3입니다.bisect_left는 동등값들 앞을, bisect_right는 동등값들 뒤를 반환합니다. 결과는 반열린 구간이며 두 경계의 차가 개수입니다.