Python bisect 라이브러리 알고리즘 활용

개요

이분 탐색(Binary Search)는 알고리즘 문제를 풀다보면 많이 만나는 문제유형이다. 매번 코딩해서 바이너리 서치를 구현해도 좋지만 문제를 많이 풀다보면 매번 구현하기에 피로가 느껴지기 쉽다. 그래서 본인이 생각하는 접근이 맞는지 빨리 확인하고 문제 푸는 용도로 라이브러리를 사용하면 유용한 것 같다. 

 

다음 리트코드 문제를 예시로 bisect 모듈을 사용 예시를 보이겠다.

•   34. Find First and Last Position of Element in Sorted Array

사용 예시

문제 설명 자체는 간단하다. Non-decreasing (증가하는) 순서로 주어진 리스트에서 주어진 값의 시작과 마지막 인덱스를 반환하는 문제인다.

 

bisect.bisect_left는 타겟 값중 가장 작은 인덱스(1). 타겟이 없으면 타겟보다 작지만 가장 근접한 인덱스 반환(2),

bisect.bisect_right는 타겟 값보다 큰 값중 가장 작은 인덱스이다.

그래서 타겟이 존재한다고 가정하면 [bisect_left(...), bisect_right(...)-1]이 된다.

하지만 타겟이 없는 경우를 방어하기 위해서 빈 리스트가 들어오거나 bisect_left의 (2)번 케이스를 if 문으로 걸러주면 된다.

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left_bound = bisect.bisect_left(nums, target)
        right_bound = bisect.bisect_right(nums, target)
        
        if len(nums) == 0:
          return [-1, -1]
        
        if left_bound >= len(nums) or nums[left_bound] != target:
          return [-1, -1]
        
        return [left_bound, right_bound-1]