Lower Bound

1. Lower Bound 알고리즘이란?

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

Lower Bound 알고리즘의 특별한 점은 무엇일까요?

기준 값 $N$ 값 이상이 처음 나타나는 위치(Index)를 찾기 위해 단순히 배열의 첫 번째 위치부터 순차적으로 탐색한다면 최악의 경우 배열의 길이만큼 끝까지 탐색을 해야 할 수 있고, 이 경우 시간복잡도는 $O(n)$이 될 것입니다.

하지만, 배열의 처음부터 탐색하지 않고 이분 탐색을 활용한다면 $O(log n)$의 시간복잡도로 탐색이 가능하며, 이것이 Lower Bound 알고리즘의 특별한 점이라고 할 수 있습니다.

2. Lower Bound의 단계별 설명

이분 탐색은 전체 배열의 중간 값과 기준 값을 비교하며 원하는 값을 찾아가는 방식입니다. Lower Bound에서도 이분 탐색과 동일하게 left, mid, right 값을 갱신하며 기준 값 $N$ 이상이 처음 나타나는 위치(Index)를 찾아갑니다.

이분 탐색 기반의 Lower Bound 알고리즘을 함께 단계별로 살펴봅시다.
특히, 주어진 배열에 기준 값 $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는 8보다 왼쪽 영역에 위치하므로 탐색 영역을 더 좁혀볼 수 있습니다.
  • 탐색 영역의 왼쪽 끝 위치 left = 0 (유지)
  • 탐색 영역의 오른쪽 끝 위치 right = mid - 1 = 6

[3] 2차 이분 탐색

• 1차 이분 탐색과 마찬가지로 좁혀진 탐색 영역의 중간 위치를 갱신해줍니다. mid = (left + right) / 2 = 3
• 이때 arr[mid] = 3이며, 기준 값 5는 3보다 오른쪽 영역에 위치하므로 탐색 영역을 더 좁혀볼 수 있습니다.
  • 탐색 영역의 왼쪽 끝 위치 left = mid + 1 = 4
  • 탐색 영역의 오른쪽 끝 위치 right = 6 (유지)

[4] 3차 이분 탐색

• 이어서 동일하게 좁혀진 탐색 영역의 중간 위치를 갱신해줍니다. mid = (left + right) / 2 = 5
• 이때 arr[mid] = 6이며, 기준 값 5는 6보다 왼쪽 영역에 위치하므로 탐색 영역을 더 좁혀볼 수 있습니다.
  • 탐색 영역의 왼쪽 끝 위치 left = 4 (유지)
  • 탐색 영역의 오른쪽 끝 위치 right = mid - 1 = 4

[5] 탐색 종료

• left와 right가 동일해졌습니다. 이때 right가 가리키는 위치 4가 기준 값 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이며, 기준 값 12는 8보다 크기 때문에 탐색 영역을 오른쪽으로 좁힙니다.
  • 탐색 영역의 왼쪽 끝 위치 left = mid + 1 = 8
  • 탐색 영역의 오른쪽 끝 위치 right = 14 (유지)

[3] 2차 이분 탐색

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

[4] 3차 이분 탐색

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

[5] 4차 이분 탐색

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

[6] 탐색 종료

• left와 right가 역전되었습니다. 이 경우, left는 더 이상 탐색할 범위가 없다는 뜻입니다. 탐색이 종료되었고, left = 11에서 12 이상인 값이 처음 등장하는 위치를 찾을 수 있습니다.
• 최종적으로 left = 11, 배열에서 12 이상인 값이 처음 나타나는 위치는 인덱스 11에서 13입니다.

---

3. Lower Bound 함수 구현 (Python, Cpp)

Python

def lower_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

Cpp

int lower_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;
}