Python에서는 bisect 모듈을 활용해 손쉽게 이진 검색(Binary Search)을 구현할 수 있습니다. 이진 검색은 정렬된 리스트에서 특정 요소를 빠르게 찾아내는 대표적인 탐색 기법으로, 매 단계마다 탐색 범위를 절반씩 줄여나가기 때문에 시간 복잡도가 O(log n)으로 매우 효율적입니다.
이 글에서는 bisect 모듈을 사용하여 다음 세 가지 작업을 수행하는 방법을 살펴보겠습니다.
- 정렬된 리스트에서 특정 요소의 첫 번째 위치 찾기
- x보다 작은 값 중 가장 큰 값 찾기
- 특정 요소의 마지막(가장 오른쪽) 위치 찾기
1. 요소의 첫 번째 등장 위치 찾기
bisect.bisect_left(a, x, lo=0, hi=len(a)) 함수는 정렬된 리스트 a에서 x가 삽입될 수 있는 가장 왼쪽 삽입 지점(leftmost insertion point)을 반환합니다. 마지막 두 매개변수인 lo와 hi는 선택 사항이며, 리스트 전체가 아닌 일부 구간(서브리스트)만 탐색하고 싶을 때 유용하게 사용됩니다.
bisect_left의 반환값이 리스트 길이와 같지 않고, 해당 인덱스의 값이 x와 일치한다면 그것이 바로 첫 번째 등장 위치입니다.
예제 코드
from bisect import bisect_left
def BinSearch(a, x):
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
else:
return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(4)
pos = BinSearch(a, x)
if pos == -1:
print(x, "is absent")
else:
print("First occurrence of", x, "is at position", pos)실행 결과
First occurrence of 4 is at position 2
리스트에 4가 두 개 존재하지만(인덱스 2와 3), bisect_left를 사용했기 때문에 가장 먼저 나타나는 인덱스 2가 반환됩니다.
2. x보다 작은 값 중 가장 큰 값 찾기
bisect_left를 응용하면 x(key)보다 작은 값들 중에서 가장 큰 값, 즉 x 바로 앞에 있는 요소를 찾을 수 있습니다. bisect_left가 반환하는 삽입 지점에서 1을 뺀 인덱스가 곧 그 위치가 됩니다.
단, x가 리스트의 최솟값보다 작거나 같아서 삽입 지점이 0이 되는 경우에는 조건에 맞는 값이 없으므로 -1을 반환하도록 처리합니다.
예제 코드
from bisect import bisect_left
def BinSearch(a, x):
i = bisect_left(a, x)
if i:
return i - 1
else:
return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(8)
pos = BinSearch(a, x)
if pos == -1:
print(x, "is absent")
else:
print("Larger value, smaller than", x, "is at position", pos)실행 결과
Larger value, smaller than 8 is at position 4
8보다 작은 값 중 가장 큰 값은 5이며, 이는 인덱스 4에 위치합니다.
3. 요소의 마지막(가장 오른쪽) 등장 위치 찾기
bisect.bisect_right(a, x, lo=0, hi=len(a)) 함수는 정렬된 리스트 a에서 x가 삽입될 수 있는 가장 오른쪽 삽입 지점(rightmost insertion point)을 반환합니다. bisect_left와 마찬가지로 lo와 hi 매개변수는 선택 사항이며, 서브리스트 탐색에 활용할 수 있습니다.
중복된 값이 여러 개 있을 때 bisect_right를 사용하면 해당 값 중 마지막으로 등장하는 인덱스를 구할 수 있습니다.
예제 코드
from bisect import bisect_right
def BinSearch(a, x):
i = bisect_right(a, x)
if i != len(a) + 1 and a[i - 1] == x:
return i - 1
else:
return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(36)
pos = BinSearch(a, x)
if pos == -1:
print(x, "is absent")
else:
print("Right most occurrence of", x, "is at position", pos)실행 결과
Right most occurrence of 36 is at position 9
리스트에 36이 세 번 등장하지만(인덱스 7, 8, 9), bisect_right 덕분에 마지막 등장 위치인 인덱스 9를 얻을 수 있습니다.
정리
Python의 bisect 모듈은 정렬된 데이터에서 반복문 없이도 효율적인 이진 검색을 가능하게 해주는 강력한 도구입니다. bisect_left는 왼쪽 삽입 지점을, bisect_right는 오른쪽 삽입 지점을 반환하므로, 이 두 함수의 동작 원리만 정확히 이해하면 첫 번째/마지막 등장 위치 찾기, 경계값 탐색 등 다양한 검색 문제를 간결한 코드로 해결할 수 있습니다.