파이썬 이진 탐색 내장 모듈 - bisect

파이썬에는 bisect 라는 배열 이진 검색을 지원하는 내장 모듈이 있습니다. 내장 모듈인 만큼 pip 를 통해 설치할 필요가 없고 파이썬 설치와 동시에 사용할 수 있습니다.

bisect는 이진 탐색을 구현하면서 이미 정렬된 배열에 대해 특정 원소 (target) 를 삽입했을 때, 다시 정렬할 필요가 없도록 관리하는 모듈로 이진 탐색 개요 포스트에서 처럼 타겟이 없을 때 -1을 return하는 것이 아니라 타겟이 정렬이 필요없을 삽입 위치의 인덱스를 return합니다.

모듈인 만큼 여러 함수가 있지만 이 포스트에서는 주로 쓰이는 bisect_left, bisect_right 에 대해 알아보도록 하겠습니다.

bisect_left(a, x, lo=0, hi=len(a))

입력 파라미터를 살펴보면,

• a: 대상 array 입니다. 이진 검색이니 이미 정렬된 array여야 합니다.
• x: target입니다. 
• lo, hi: 주어진 array에 대해 고려해야 할 배열 부분집합을 지정합니다.

bisect_left에서 left의 의미는 x 값이 a에 이미 있을 때, x가 삽입될 위치는 a의 기존 항목 왼쪽을 return한다는 뜻입니다. 배열 [1,3,5,7,9]에 대해 한 번 살펴보겠습니다.

간단 실험

• 일단 x=3 일 때, 어떤 값을 return하는 지 확인해 보겠습니다. 위에서 설명한대로 a에 이미 3이 있으니 기존 3의 왼쪽 인덱스인 1을 반환합니다.

• 그 다음 lo를 1, 2, 3로 지정하고 x를 5라 했을 때, 어떤 값을 return하는지 확인해 봤을 때, lo가 1,2일 때 2, 3일 때 3이 return됩니다.
• bisect 문서를 살펴보면 bisect_left에서 return된 인덱스를 i라 했을 때, a[lo:i]는 target보다 무조건 작고 a[i:hi]는 target보다 무조건 같거나 커야 합니다. 따라서, lo 값이 지정될 경우 반환되는 인덱스는 lo보다 작을 수 없습니다. 
• 간단히 생각하면 lo의 인덱스가 타겟 인덱스 (bisect_left에서는 2) 보다 작다면 같다면 타겟 인덱스를 그대로 return하고 타겟 인덱스보다 크다면 lo값을 그대로 return합니다.

• 배열의 slicing을 하고 타겟 5를 찾아보겠습니다. a[1:] = [3,5,7,9] 이므로 x=5에 대해 1을 return하여야 합니다.

 

bisect_right(a, x, lo=0, hi=len(a))

bisect_left와 거의 비슷하나 a에 x가 이미 있을 경우 기존 항목의 오른쪽 인덱스를 반환합니다.

간단 실험

• 일단 x=3 일 때, 어떤 값을 return하는 지 확인해 보겠습니다. 위에서 설명한대로 a에 이미 3이 있으니 기존 3의
  오른쪽 인덱스인 2을 반환합니다.

• 그 다음 lo를 1, 2, 3, 4로 지정하고 x를 5라 했을 때, 어떤 값을 return하는지 확인해 보겠습니다. lo가 1,2,3일 때 3을 return하고 4일 때 4를 return합니다. 
• bisect 문서를 살펴보면 bisect_right에서 return된 인덱스를 i라 했을 때, a[lo:i]는 target보다 무조건 작거나 같고 a[i:hi]는 target보다 무조건 커야 합니다.
• bisect_left 시와 마찬가지로 lo 인덱스가 타겟 인덱스 (bisect_right 에선 3) 보다 작거나 같다면 타겟 인덱스를 return하고 타겟 인덱스보다 클 경우 lo 인덱스를 return한다고 생각할 수 있습니다.

 

홍머스 정리

• 이진 검색은 bisect, 값이 있을 경우 왼쪽 인덱스 return은 bisect_left, 오른쪽 인덱스 return은 bisect_right
• 입력 파라미터의 lo, hi를 지정하는 것과 a를 slicing해서 넣는 것은 다르다. lo, hi는 입력 a를 slicing하는 것이 아니라 lo-hi 사이에서 값을 비교하여 반환할 인덱스를 정하는 용도로 사용.
• 반환되는 인덱스는 lo-hi 사이!
• 온라인 코딩테스트에서는 bisect를 사용해도 괜찮겠지만 온사이트 인터뷰 시 이진 탐색 직접 구현을 물어볼 수 있으므로 숙지하자!

참조

• docs.python.org/ko/3/library/bisect.html