이진트리

Lower Bound와 Upper Bound 구현하기

정의

• Lower Bound: 주어진 값 x 이상인 정렬된 배열의 첫 번째 위치를 찾는 연산이다. 즉, x 이상이 되는 요소 중 가장 왼쪽에 있는 요소의 인덱스를 반환한다.
• Upper Bound: 주어진 값 x를 초과하는 정렬된 배열의 첫 번째 위치를 찾는 연산이다. 여기서는 x를 초과하는 요소 중 가장 왼쪽에 있는 요소의 인덱스를 반환한다.

구현 방법

이진 탐색을 응용하여 Lower Bound와 Upper Bound를 효율적으로 구할 수 있다. 정렬된 배열이 주어졌을 때, 이진 탐색을 변형하여 주어진 조건에 맞는 위치를 찾는다.

Lower Bound 구현

Lower Bound를 찾는 함수는 다음과 같이 구현할 수 있다. 주어진 값 x 이상이 되는 배열 내 첫 번째 위치를 찾아 반환한다.

def lower_bound(arr, x):
    left, right = 0, len(arr)  # 탐색 시작점과 끝점 설정
    while left < right:  # 탐색 범위가 남아있는 동안
        mid = (left + right) // 2  # 중간점 계산
        if arr[mid] < x:  # 중간 값이 x 미만일 경우
            left = mid + 1  # 탐색 범위를 오른쪽 절반으로 조정
        else:  # 중간 값이 x 이상일 경우
            right = mid  # 탐색 범위를 왼쪽 절반(포함)으로 조정
    return left  # x 이상이 되는 첫 번째 위치 반환

Upper Bound 구현

Upper Bound를 찾는 함수는 다음과 같이 구현할 수 있다. 주어진 값 x를 초과하는 배열 내 첫 번째 위치를 찾아 반환한다.

def upper_bound(arr, x):
    left, right = 0, len(arr)  # 탐색 시작점과 끝점 설정
    while left < right:  # 탐색 범위가 남아있는 동안
        mid = (left + right) // 2  # 중간점 계산
        if arr[mid] <= x:  # 중간 값이 x 이하일 경우
            left = mid + 1  # 탐색 범위를 오른쪽 절반으로 조정
        else:  # 중간 값이 x 초과일 경우
            right = mid  # 탐색 범위를 왼쪽 절반(포함)으로 조정
    return left  # x를 초과하는 첫 번째 위치 반환

결론

Lower Bound와 Upper Bound는 정렬된 배열에서 특정 조건을 만족하는 요소의 위치를 찾기 위한 강력한 도구이다. 이진 탐색을 기반으로 하는 이들 연산은 O(log n)의 시간 복잡도로 동작하며, 다양한 알고리즘 문제 해결에 활용될 수 있다.