Upper Bound

1. Upper Bound 알고리즘이란?

Upper Bound는 이분 탐색에 기반한 알고리즘으로 오름차순 정렬된 배열과 기준 값 $N$ 이 주어졌을 때 기준 값 $N$ 보다 큰 값이 처음 나타나는 위치(Index) 를 찾는 알고리즘입니다.

배열을 처음부터 끝까지 순차적으로 탐색한다면 최악의 경우 배열의 길이만큼 끝까지 탐색해야 할 수 있습니다. 이 경우 시간 복잡도는 $O(n)$이 될 것입니다.

그러나 배열의 처음부터 순차 탐색하지 않고 이분 탐색을 사용한다면, $O(log n)$의 시간 복잡도로 더 효율적으로 탐색할 수 있습니다.
이 부분이 Upper Bound 알고리즘의 특별한 점입니다.

2. Upper Bound의 단계별 설명

Upper Bound는 이분 탐색을 기반으로 left, mid, right 값을 갱신하며 기준 값보다 큰 값이 처음 나타나는 위치를 찾는 방식입니다. 배열에 기준 값 $N$이 존재하는지에 따라 Case를 나누어 살펴보겠습니다.

1. 배열 안에 기준값이 존재하는 경우

[1] 초기 상태

• 배열: arr = [1, 2, 3, 3, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 18] (배열의 길이 = 15)
• 기준 값: 5

배열의 길이가 15이고, 초기 탐색 영역은 배열 전체이므로 아래와 같이 설정할 수 있습니다.

• 탐색 영역의 왼쪽 끝 위치 left = 0
• 탐색 영역의 오른쪽 끝 위치 right = 14

[2] 1차 이분 탐색

• 배열의 중간 위치 mid를 갱신합니다. mid = (left + right) // 2 = 7
• 이때 arr[mid] = 8이며, 기준 값 5보다 크므로 더 작은 영역으로 탐색 영역을 좁힙니다.
  • 탐색 영역의 왼쪽 끝 위치 left = 0 (유지)
  • 탐색 영역의 오른쪽 끝 위치 right = mid = 7

[3] 2차 이분 탐색

• 중간 위치 mid를 갱신합니다. mid = (left + right) // 2 = 3
• 이때 arr[mid] = 3으로 기준 값 5보다 작기 때문에 탐색 영역을 더 오른쪽으로 좁힙니다.
  • 탐색 영역의 왼쪽 끝 위치 left = mid + 1 = 4
  • 탐색 영역의 오른쪽 끝 위치 right = 7 (유지)

[4] 3차 이분 탐색

• 중간 위치 mid를 갱신합니다. mid = (left + right) // 2 = 5
• 이때 arr[mid] = 6으로, 기준 값보다 크기 때문에 탐색 영역을 왼쪽으로 좁힙니다.
  • 탐색 영역의 왼쪽 끝 위치 left = 4 (유지)
  • 탐색 영역의 오른쪽 끝 위치 right = mid = 5

[5] 탐색 종료

• left와 right가 만났습니다. 이때 right가 가리키는 위치 5는 기준 값 5보다 큰 값이 처음 나타나는 위치입니다.

---

2. 배열 안에 기준값이 존재하지 않는 경우

[1] 초기 상태

• 배열: arr = [1, 2, 3, 3, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 18] (배열의 길이 = 15)
• 기준 값: 12

배열의 길이가 15이고, 기준 값 12를 찾기 위한 탐색 영역은 배열 전체이므로 아래와 같이 설정할 수 있습니다.

• 탐색 영역의 왼쪽 끝 위치 left = 0
• 탐색 영역의 오른쪽 끝 위치 right = 14

[2] 1차 이분 탐색

• 중간 위치 mid를 갱신합니다. mid = (left + right) // 2 = 7
• 이때 arr[mid] = 8로, 기준 값보다 작기 때문에 탐색 영역을 오른쪽으로 좁힙니다.
  • 탐색 영역의 왼쪽 끝 위치 left = mid + 1 = 8
  • 탐색 영역의 오른쪽 끝 위치 right = 14 (유지)

[3] 2차 이분 탐색

• 중간 위치 mid를 갱신합니다. mid = (left + right) // 2 = 11
• 이때 arr[mid] = 13으로, 기준 값보다 크기 때문에 탐색 영역을 왼쪽으로 좁힙니다.
  • 탐색 영역의 왼쪽 끝 위치 left = 8 (유지)
  • 탐색 영역의 오른쪽 끝 위치 right = mid = 11

[4] 3차 이분 탐색

• 중간 위치 mid를 갱신합니다. mid = (left + right) // 2 = 9
• 이때 arr[mid] = 10으로, 기준 값보다 작기 때문에 탐색 영역을 오른쪽으로 좁힙니다.
  • 탐색 영역의 왼쪽 끝 위치 left = mid + 1 = 10
  • 탐색 영역의 오른쪽 끝 위치 right = 11 (유지)

[5] 4차 이분 탐색

• 마지막으로 중간 위치 mid를 갱신합니다. mid = (left + right) // 2 = 10
• 이때 arr[mid] = 11로, 기준 값보다 작기 때문에 탐색 영역을 다시 오른쪽으로 좁힙니다.
  • 탐색 영역의 왼쪽 끝 위치 left = mid + 1 = 11
  • 탐색 영역의 오른쪽 끝 위치 right = 11 (유지)

[6] 탐색 종료

• left와 right가 만났습니다. 이때 left가 가리키는 위치는 기준 값보다 큰 값이 처음 나타나는 위치입니다. left = 11에서 기준 값보다 큰 값은 13입니다.

3. Upper Bound 함수 구현 (Python, C++)

Python

def upper_bound(nums, target):
    left, right = 0, len(nums)
    
    while left < right:  # left와 right가 만나는 지점이 target보다 큰 값이 처음 나오는 위치
        mid = (left + right) // 2
        
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid
    
    return left

Python에서는 bisect 모듈에 upperbound 메소드가 존재합니다.

C++

int upper_bound(const std::vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size();  // vector의 크기

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return right;
}