파이썬에서는 이진 탐색을 포함하여 다양한 탐색 알고리즘을 지원하는 라이브러리가 내장되어 있습니다. 이를 이용하면 손쉽게 이진 탐색을 구현할 수 있습니다.
파이썬에서는 bisect 모듈을 이용하여 이진 탐색을 구현할 수 있습니다. bisect 모듈은 정렬된 리스트에서 특정 값을 찾는 것이 아니라, 해당 값이 들어갈 위치를 찾는 데 사용됩니다. 따라서 bisect 모듈은 이진 탐색보다 더 일반적인 용도로 사용됩니다.
bisect_left 함수
bisect_left 함수는 정렬된 리스트에서 특정 값이 들어갈 위치(인덱스)를 찾습니다. 만약 해당 값이 이미 리스트에 존재한다면, 해당 값이 위치한 가장 왼쪽 인덱스를 반환합니다. bisect_left 함수는 다음과 같은 구문을 갖습니다.
bisect_left(arr, x, lo=0, hi=None)
- arr: 탐색할 정렬된 리스트
- x: 찾을 값
- lo: 탐색 범위의 최소 인덱스(default: 0)
- hi: 탐색 범위의 최대 인덱스(default: len(arr))
bisect_left 함수 예제
import bisect
arr = [1, 3, 5, 7, 9]
x = 5
y = 7
indexX = bisect.bisect_left(arr, x)
indexY = bisect.bisect_left(arr, y)
print(indexX)
print(indexY)결과
2
3위 코드에서는 arr 리스트에서 x, y 값이 들어갈 위치(인덱스)를 찾아내고 출력하고 있습니다. 이 경우 x 값은 arr [2], y값은 arr [3]에 들어가게 됩니다.
bisect_right 함수
bisect_right 함수는 bisect_left 함수와 동일한 역할을 수행합니다. 다만, 해당 값이 이미 리스트에 존재한다면, 해당 값이 위치한 가장 오른쪽 인덱스의 다음 인덱스를 반환합니다. bisect_right 함수는 다음과 같은 구문을 갖습니다.
bisect_right(arr, x, lo=0, hi=None)- arr: 탐색할 정렬된 리스트
- x: 찾을 값
- lo: 탐색 범위의 최소 인덱스(default: 0)
- hi: 탐색 범위의 최대 인덱스(default: len(arr))
bisect_right 함수 예제
다음과 같이 리스트를 정의하고 bisect_right 함수를 사용할 수 있습니다.
import bisect
arr = [1, 3, 5, 5, 7, 9]
x = 5
y = 9
indexX = bisect.bisect_right(arr, x)
indexY = bisect.bisect_right(arr, y)
print(indexX)
print(indexY)결과
4
6
bisect 함수
bisect 함수는 bisect_left 함수와 bisect_right 함수의 결합체입니다. 즉, 해당 값이 이미 리스트에 존재한다면, 해당 값이 위치한 가장 오른쪽 인덱스의 다음 인덱스를 반환합니다. bisect 함수는 다음과 같은 구문을 갖습니다.
bisect(arr, x, lo=0, hi=None)- arr: 탐색할 정렬된 리스트
- x: 찾을 값
- lo: 탐색 범위의 최소 인덱스(default: 0)
- hi: 탐색 범위의 최대 인덱스(default: len(arr))
파이썬 bisect 함수 예제
import bisect
arr = [1, 3, 5, 5, 7, 9]
x = 5
index = bisect.bisect(arr, x)
print(index)위 코드에서는 arr 리스트에서 x 값이 들어갈 위치(인덱스)를 찾아내고 출력하고 있습니다. 이 경우 x 값이 arr[4]에 들어가게 됩니다.
위와 같은 방법으로 파이썬에서는 이분 탐색을 쉽게 구현할 수 있습니다. 이분 탐색을 이용하여 문제를 풀 때에는 bisect 모듈을 이용하여 효율적인 구현을 고려해 보는 것이 좋습니다.
댓글