[Algorithm] Lower bound / Upper bound

0. lower bound / upper bound란?

 

만약 내가 찾는 값(타겟)이 배열에 여러 개 있다면, 이진 탐색을 실행했을 때 어떤 위치가 나오게 될 지 모른다. 따라서 우리는 이런 경우를 방지하고자 lower bound, upper bound를 사용한다. 

 

lower bound란 타겟 이상의 값이 최초로 나오는 위치를 의미한다. upper bound란 타겟을 초과하는 값이 최초로 나오는 위치를 의미한다. 따라서 타겟은 lower bound와 upper bound 사이에 있을 것이므로, 타겟이 여러 개일 때 타겟의 갯수를 세는 것이 가능해진다.

 

만약 타겟이 배열 내에 없다면, upper bound - lower bound = 0이 될 것이다. 타겟 이상의 값과 타겟 초과의 값이 동일하다는 것은 타겟이 없다는 것을 의미하기 때문이다. 

 

1. 구현

 

a = input()
n_m = a.split()
n = int(n_m[0])
m = int(n_m[1])
nums = input()
num = nums.split()

targets = []
for i in range(n):
    num[i] = (int)(num[i])
for i in range(m):
    targets.append(int(input()))

def lower_bound(num, target):
    left = 0
    right = len(num) - 1
    min_idx = len(num)

    while left <= right:
        mid = (int)((left + right) / 2)
        if num[mid] >= target:
            right = mid - 1
            min_idx = min(mid, min_idx)
        else:
            left = mid + 1

    return min_idx

def upper_bound(num, target):
    left = 0
    right = len(num) - 1
    min_idx = len(num)

    while left <= right:
        mid = (int)((left + right) / 2)
        if num[mid] > target:
            right = mid - 1
            min_idx = min(mid, min_idx)
        else:
            left = mid + 1

    return min_idx

res = []

for i in range(m):
    res_value = upper_bound(num, targets[i]) - lower_bound(num, targets[i])
    print(res_value)

문제 링크: https://www.codetree.ai/missions/6/concepts/31/problems/number-of-integers/description

코드트리

 

n개의 숫자가 오름차순으로 정렬된 상태로 주어지고, m개의 타겟이 주어진다. 목표는 m개의 각각의 숫자가 처음 주어진 n개의 숫자 중 몇 번 나왔는지를 구하는 것이다. 

 

1) lower_bound

이진 탐색을 통해 타겟을 찾는다. 이 때 index의 최솟값을 찾음으로써 타겟이 시작하는 위치를 찾을 수 있다. 

 

2) upper_bound

이진 탐색을 통해 타겟을 찾는다. 이 때 index의 최솟값을 찾음으로써 타겟의 끝 위치를 알 수 있다.