binary search 를 위한 bisect 모듈

이분탐색은 이미 정렬이 된 자료에서 내가 목표하는 값(target value)의 위치(index)를 자료를 반으로 나누어 탐색하는 과정을 반복하는 방법을 말한다. 이 경우 O(logn) 시간에 결과를 찾게 된다.

bisect 모듈을 이용하면 쉽게 이를 수행할 수 있다. bisect_left는 목표값과 같거나 큰 첫 숫자의 인덱스를, bisect_right과 bisect는 목표값보다 큰 첫 숫자의 인덱스를 돌려준다. 함수들의 첫번째 인자는 검색대상이 되는 정렬된 리스트, 두번째 인자는 찾으려는 목표값이다.

import bisect

bisect.bisect_left([.5, .8, .9, 1], .5)    # 0
bisect.bisect_right([.5, .8, .9, 1], .5)   # 1
bisect.bisect([.5, .8, .9, 1], .5)         # 1

bisect.bisect_left([.5, .8, .9, 1], .45)   # 0
bisect.bisect_right([.5, .8, .9, 1], .45)  # 0
bisect.bisect([.5, .8, .9, 1], .45)        # 0

정의를 정확히 알면 여러가지 다양한 경우에도 대응할 수 있다. 위의 예를 보면, 정의 그대로 수행하고 있음을 확인할 수 있다. 맨 첫 예인 bisect_left는 0.5 목표값을 탐색시 맨 첫 인덱스의 숫자가 같거나 크므로 그 인덱스인 0을 돌려준다. 그 아래 bisect_right과 bisect는 0.5 목표값 보다 큰 첫 숫자(.8)의 인덱스인 1을 돌려준다. 그 아래 예시도 확인해 보기 바란다.