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, hi=len(a)))와 동일
  • bisect.insort_right(a, x, lo=0, hi=len(a))
    • a.insert(bisect_right(a, x, lo=0, hi=len(a)))와 동일
  • bisect.insort(a, x, lo=0, hi=len(a))
    • bisect.insort_right의 alias

실제로 리스트를 만들어서 실험해보면, 별도의 자료구조를 생성하지 않고도 아래와 같이 편리하게 이진 탐색 기능을 쓸 수 있는걸 확인할 수 있습니다.

>> import bisect
>> A = [33, 70, 89, 90, 100]
>> bisect.bisect_left(A, 70)
1
>> bisect.bisect_right(A, 70)
2
>> bisect.bisect(A, 70)
2

Comments

Popular posts from this blog

유튜브 추천시스템 논문 리뷰 Part 2 - Deep Neural Networks for YouTube Recommendations (RecSys 2016)

맥락 기반(Context-aware) 추천 시스템은 어떻게 만드는가?

유튜브 추천시스템 논문 리뷰 Part 1 - The Youtube Video Recommendation System (RecSys 2010)