lower bound with bisect_left (python)
C++에 [[이분탐색을 활용한 lowerbound 구현법 {Algo}|lower_bound]]가 있다면 파이썬에는 bisect.bisect_left가 있다. 그럼 upper_bound는? bisect.bisect_right 바보야 😲
이분탐색은 그 자체로 너무 많은 곳에 활용이 되고 있어서 실전 위주로 정리를 해보겠다. 흠흠
아래는 LIS 가장 긴 증가하는 부분수열를 파이썬으로 구현한 코드이다. 확실히 엄청나게 간결하다.
아래는 삽입정렬을 bisect_left를 활용하여 푼 코드이다. 부분정렬리스트인데, 이분탐색을 안할 이유가 없잖아?