Lower Bound와 Upper Bound에서 left, right 갱신 방식의 차이
이분 탐색 기반의 알고리즘에서 Lower Bound와 Upper Bound는 각각 특정 기준 값을 기준으로 배열에서 첫 번째로 등장하는 위치를 찾는 알고리즘입니다. 두 알고리즘 모두 이분 탐색을 기반으로 하지만, left와 right 값을 갱신하는 방식에서 차이가 발생합니다. 이 차이는 각각의 알고리즘이 찾고자 하는 대상이 다르기 때문입니다.
Lower Bound와 Upper Bound의 차이점과 왜 두 알고리즘에서 left와 right를 갱신하는 방식이 달라지는지 상세하게 설명해보겠습니다.
1. Lower Bound: 기준 값 이상인 값이 처음 등장하는 위치 찾기
Lower Bound는 배열에서 기준 값 이상인 값이 처음으로 나타나는 위치를 찾는 알고리즘입니다. 이를 위해 배열을 이분 탐색으로 탐색하며, 다음과 같은 방식으로 left와 right 값을 갱신합니다.
Lower Bound 갱신 방식
if nums[mid] < target:
left = mid + 1 # 기준 값보다 작은 경우는 무조건 제외하고, 오른쪽으로 탐색
else:
right = mid # 기준 값 이상이므로, 해당 mid 위치가 답일 가능성이 있어 범위를 유지갱신 방식 설명
-
if nums[mid] < target: 중간 값이 기준 값보다 작다면, 기준 값 이상이 될 가능성은 배열의 오른쪽에만 존재합니다. 따라서, left = mid + 1로 갱신하여 탐색 범위를 오른쪽으로 좁힙니다. -
else: 중간 값이 기준 값 이상이면, 해당 위치가 우리가 찾는 값일 수 있기 때문에, right = mid로 갱신하여 탐색 범위를 왼쪽까지 포함한 상태로 줄입니다. 이 경우right = mid - 1로 갱신하지 않는 이유는, 해당 위치가 답이 될 수 있기 때문입니다. right = mid를 사용함으로써 기준 값 이상인 값을 포함한 영역을 계속 탐색합니다.
예시
- 배열:
[1, 2, 3, 5, 6, 8, 9, 10] - 기준 값: 6
- 목표: 6 이상인 값이 처음 등장하는 위치 찾기
- mid = 3, nums[mid] = 5 → 기준 값보다 작으므로 left = mid + 1 = 4
- mid = 5, nums[mid] = 8 → 기준 값 이상이므로 right = mid = 5
- mid = 4, nums[mid] = 6 → 기준 값 이상이므로 right = mid = 4
결과적으로, left = right = 4에서 탐색이 종료되며, 6 이상이 처음 등장하는 위치는 인덱스 4입니다.
2. Upper Bound: 기준 값 초과인 값이 처음 등장하는 위치 찾기
반면에, Upper Bound는 배열에서 기준 값보다 큰 값이 처음으로 나타나는 위치를 찾는 알고리즘입니다. Lower Bound와 마찬가지로 이분 탐색을 기반으로 하지만, 기준 값 초과인 값만을 찾아야 하므로, 갱신 방식이 약간 다릅니다.
Upper Bound 갱신 방식
if nums[mid] <= target:
left = mid + 1 # 기준 값과 같거나 작으면 제외하고, 오른쪽으로 탐색
else:
right = mid - 1 # 기준 값보다 크므로, 더 작은 값을 탐색해야 함갱신 방식 설명
-
if nums[mid] <= target: 중간 값이 기준 값보다 작거나 같으면, 해당 값 이후의 값들만 기준 값보다 클 수 있으므로, left = mid + 1로 갱신하여 탐색 범위를 오른쪽으로 좁힙니다. 기준 값과 같은 값은 우리가 찾는 값이 아니기 때문에, 반드시 초과하는 값만을 찾아야 합니다. -
else: 중간 값이 기준 값보다 크면, right = mid - 1로 갱신하여 더 작은 범위를 탐색합니다. 이때, mid 위치는 이미 기준 값보다 큰 값이므로, 해당 값을 포함하지 않고 바로 왼쪽으로 범위를 좁히기 위해 right = mid - 1로 갱신합니다.
예시
- 배열:
[1, 2, 3, 5, 6, 8, 9, 10] - 기준 값: 6
- 목표: 6을 초과하는 값이 처음 등장하는 위치 찾기
- mid = 3, nums[mid] = 5 → 기준 값보다 작으므로 left = mid + 1 = 4
- mid = 5, nums[mid] = 8 → 기준 값보다 크므로 right = mid - 1 = 4
- mid = 4, nums[mid] = 6 → 기준 값과 같으므로 left = mid + 1 = 5
결과적으로, left = 5에서 탐색이 종료되며, 6을 초과하는 값이 처음 등장하는 위치는 인덱스 5에서 8입니다.
Lower Bound와 Upper Bound 갱신 방식의 차이 요약
두 알고리즘은 이분 탐색을 기반으로 하지만, 다음과 같은 이유로 left와 right를 갱신하는 방식에서 차이를 보입니다.
-
Lower Bound: 기준 값 이상인 첫 번째 위치를 찾기 때문에, 기준 값 이상인 값이 나올 때 그 값을 포함하는 방식으로 탐색을 진행합니다. 따라서,
right = mid를 사용하여 해당 값을 포함한 탐색을 유지합니다. -
Upper Bound: 기준 값보다 큰 첫 번째 값을 찾아야 하므로, 기준 값과 같거나 작은 값이 나오면 그 값을 제외하고 탐색을 진행합니다. 따라서,
right = mid - 1을 사용하여 해당 값을 제외하고 탐색 범위를 줄입니다.
Lower Bound와 Upper Bound의 핵심 차이
- Lower Bound는 기준 값과 같은 값도 찾는 대상이므로, 기준 값과 같으면 포함하는 방향으로 탐색을 진행합니다.
- Upper Bound는 기준 값보다 큰 값을 찾기 때문에, 기준 값과 같으면 제외하고 탐색을 진행합니다.
이 차이가 left와 right 갱신 방식에서 나타나는 핵심 이유입니다.
이처럼 Lower Bound와 Upper Bound는 이분 탐색을 사용하여 배열에서 특정 값을 효율적으로 찾는 알고리즘이지만, 찾고자 하는 값의 조건에 따라 탐색 범위를 줄이는 방식에서 차이가 발생합니다. 이 차이를 정확히 이해하는 것이 중요하며, 이를 통해 이분 탐색 알고리즘을 다양한 상황에 맞게 활용할 수 있습니다.
