Lower bound, Upper bound

프로그래머스 문제를 풀다가 lower bound를 이용해서 풀면 좋은 문제가 있었다.

따라서 lower bound가 무엇인지 공부하면서 내용을 정리해보고자 한다.

 

lower bound와 upper bound는 이진 탐색 트리를 포스팅한 글에서 적은 bisect 모듈과 같은 기능을 한다.

lower bound는 bisect_left, upper bound는 bisect_right라고 보면된다.

🍀 Lower Bound

- target 값이 들어갈 수 있는 첫 번 째 인덱스를 반환한다.

 

구현 코드는 다음과 같다.

def lower_bound(nums, target):

    left, right = 0, len(nums)

    while left < right:
        mid = (left+right) // 2

        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid

    return right

이진 탐색 때 사용했던 코드를 조금 변형해서 구현했다.

while문을 돌면서 중간 값 인덱스를 계산하고, 중간값이 target보다 작으면 left를 mid+1로 옮긴다.

어차피 중간값은 target보다 작기 때문에 mid가 아닌 mid+1로 옮기는 것이다.

 

중간값이 target보다 같거나 큰 경우는 rignt를 mid로 옮긴다.

🍀 Upper Bound

- target 값이 들어갈 수 있는 마지막 인덱스를 반환한다.

 

구현 코드는 다음과 같다.

def upper_bound(nums, target):

    left, right = 0, len(nums)

    while left < right:
        mid = (right+left) // 2

        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid

    return right

    

while문을 돌면서 중간 값 인덱스를 계산하고, 중간값이 target보다 같거나 작으면 left를 mid+1로 옮긴다.

upper bound의 경우, target과 중간 값이 같으면 다음 인덱스를 찾아야 하기 때문에 target과 중간 값이 같은 경우도 넣어주는 것이다.

 

중간값이 target보다 큰 경우는 rignt를 mid로 옮긴다.