이진 검색(binary search)은 정렬된 배열에서 빠르게 원소를 찾을 수 있는 방법 ( \( O( log n ) \) )이다. 배열이 정렬이 되어 있으므로, 중간값 a[mid] 을 보고 찾으려는 값 x보다 작으면 x는 중간값의 오른쪽, 찾으려는 값 x보다 크면 중간값의 왼쪽에 있다는 사실을 이용한다. Python의 bisect 모듈에서 bisect_left, bisect_right 두 가지가 제공되는데, 확실하게 정리를 하고 넘어가자.
bisect_left(a, x)
정렬된 배열 a에 원소 x를 삽입할 위치를 반환한다. 원소 x가 a에 존재한다면 가장 왼쪽의 원소 위치를 반환한다.
bisect_right(a, x)
정렬된 배열 a에 원소 x를 삽입할 위치를 반환한다. 원소 x가 a에 존재한다면 이번에는 가장 오른쪽 원소 바로 다음 위치를 반환한다.
| 코드 | 설명 |
| bisect_left(a, 0) = 0 | 값 0을 삽입할 위치는 0번째 |
| bisect_left(a, 1) = 0 | 값 1이 배열에 있고, 값 1의 왼쪽 위치가 0번째 |
| bisect_left(a, 2) = 1 | 값 2를 삽입할 위치는 1번째 |
| bisect_left(a, 3) = 1 | 값 3의 왼쪽 위치가 1번째 |
| bisect_left(a, 4) = 4 | 값 4를 삽입할 위치는 4번째 |
| bisect_left(a, 5) = 4 | 값 5의 왼쪽 위치가 4번째 |
| bisect_left(a, 6) = 5 | 값 6를 삽입할 위치는 마지막 5번째 |
| 코드 | 설명 |
| bisect_right(a, 0) = 0 | 값 0을 삽입할 위치는 0번째 |
| bisect_right(a, 1) = 1 | 값 1이 배열에 있고, 값 1의 오른쪽 위치(포함하지 않음) 1번째 |
| bisect_right(a, 2) = 1 | 값 2를 삽입할 위치는 1번째 |
| bisect_right(a, 3) = 4 | 값 3의 오른쪽 위치가 4번째 |
| bisect_right(a, 4) = 4 | 값 4를 삽입할 위치는 4번째 |
| bisect_right(a, 5) = 5 | 값 5의 오른쪽 위치가 5번째 |
| bisect_right(a, 6) = 5 | 값 6를 삽입할 위치는 마지막 5번째 |
값 x가 배열 a에 없을 때는 bisect_left(a,x)와 bisect_right(a,x)의 반환값이 일치한다. 값이 배열에 있을 때는 가장 왼쪽의 위치를 리턴하는지, 아니면 가장 오른쪽의 위치 바로 다음을 리턴하는지의 차이다.
bisect_left(a,x)나 bisect_right(a,x)이 len(a)와 같으면 -- 가장 마지막 원소 다음 위치 -- 원소 x가 배열 a에 존재하지 않음을 알 수 있다. 왜냐하면 원소 x가 배열 a에 있는 모든 원소들보다 크기 때문이다.
그 외의 경우에는 반환값 i에 대하여 a[i]의 값이 x와 일치하는지만 체크하면 된다. x와 같다면 배열 a에 원소 x가 존재함을 알 수 있고, x와 같지 않다면 배열 a에 원소 x가 존재하지 않는 것이다.
이제 bisect_left(a,x)을 구현을 해보자.
예시에서 3을 찾는 경우를 생각해보자. 만약에 a[i] < 3 이라는 조건문을 각 원소마다 체크하면 다음과 같다.
bisect_left는 a[i] < x 를 만족하는 i 중에서 가장 작은 i를 리턴하는 것이다. 만약에 배열의 모든 값보다 더 큰 값을 찾는다면 이번에는 배열의 마지막 인덱스 바로 다음 위치를 리턴하면 된다. 즉, 가능한 값의 범위는 0, 1, 2, 3, 4, 5임.
def bisect_left(a, x):
left = 0
right = len(a)
while left < right:
mid = (left + right) // 2
if a[mid] < x:
left = mid + 1
else: # a[mid] >= x
right = mid
return left
left와 right는 구간 a[left:right]에 대응이 된다. a[mid] < x가 True라면, 적어도 mid와 그것보다 작은 원소들 중에서 x를 찾을 수 없을 것이다. left는 mid + 1, 즉 x는 a[mid+1:right]의 범위에서 검색하면 된다. 만약 a[mid] < x가 False가 나왔다고 해보자. 그러면 x는 a[left:mid]의 범위에서 찾을 수 있다. 그리고 이 루프에서 left와 right은 서로 다가가고, left == right가 되는 시점에서 while loop에서 빠져나오게 된다.
bisect_right(a,x)인 경우는 a[mid] <= x을 따져보면 된다. 여기서 3을 가장 마지막 3 다음에 넣을 수 있으므로 4를 반환한다.
bisect_left(a,x)의 코드에서 if a[mid] < x: 대신에 if a[mid] <= x: 로 고치면 그것이 bisect_right(a, x) 가 된다.