python standard 라이브러리인 bisect로 이진탐색하기
Leetcode나 TopCoder같은 알고리즘 문제은행 사이트를 돌다보면, 간혹 이진 탐색을 필요로 하는 문제를 마주칠 때가 있습니다. 저는 주 언어로 Python을 사용하기 때문에 보통 python으로 문제를 푸는데요, python solution들을 보면 이진 탐색을 직접 구현해서 문제를 푸는 경우가 매우 많습니다. 그런데 사실, python에는 이미 standard library에 이미 bisect 라는 이진 탐색 라이브러리가 구현이 되어있어서 이진 탐색 알고리즘을 따로 짤 필요가 없습니다. 대부분의 문제은행 사이트들이 custom library 설치를 지원하지 않는다는 점을 고려하면, bisect 라이브러리의 존재는 단비같은 존재라고 할 수 있겠지요. 오늘은 이 bisect 모듈을 이용해서 어떻게 이진 탐색을 할 수 있는지를 한번 알아보도록 하겠습니다. bisect 라이브러리는 이미 정렬된 리스트 에 대해서 적용할 수 있는 이진 탐색 관련 함수들을 제공하는데요, 총 6가지 함수들이 있습니다. bisect. bisect_left (a, x, lo=0, hi=len(a)) 정렬된 리스트 a에서 x보다 크거나 같은 첫 원소의 index를 return합니다. 만일 a의 모든 원소가 x보다 작다면 len(a)를 return합니다. lo, hi 값은 a의 특정 부분만 잘라내기 위한 half-open interval을 지정하는 용도로 쓰입니다. bisect. bisect_right (a, x, lo=0, hi=len(a)) 정렬된 리스트 a에서 x보다 큰 첫 원소의 index를 return합니다. 만일 a의 모든 원소가 x보다 작거나 같다면 len(a)를 return합니다. bisect. bisect (a, x, lo=0, hi=len(a)) bisect.bisect_right의 alias bisect. insort_left (a, x, lo=0, hi=len(a)) a.insert(bisect_left(a, x, lo=0, h
