upper bound, lower bound : 이분탐색

📌 Lower Bound(상계)

정렬되어 있는 데이터 set에서 K값 이상이 처음 발견되는 위치를 의미한다.

📌 Upper Bound(하계)

정렬되어 있는 데이터 set에서 K값보다 큰 값이 처음 발견되는 위치를 의미한다.

💡 예를 들어
1 2 2 3 3 3 4 5 의 데이터 set에서
lower bound(3) = 3, upper bound(3) = 6
@ 데이터 set의 index는 0에서부터, lower bound(찾고자 하는 숫자 = K)

✅ 이분 탐색을 이용하여 upper bound, lower bound를 구해 보자!

## lower bound
int start = 0; int end = N-1;
while(start <= end) {
	int mid = (start + end) / 2;
	if(set[mid] < K) start = mid + 1;
	else end = mid - 1;
}

System.out.println(start);

이때, start는 K값이 가장 처음으로 나오는 곳! (index)

## upper bound
int start = 0; int end = N-1;
while(start <= end) {
	int mid = (start + end) / 2;
	if(set[mid] <= K) start = mid + 1;
	else end = mid - 1;
}

System.out.println(end);

이때, end가 K값이 가장 마지막으로 나오는 곳!

💡 이분탐색은 두 그룹을 어떻게 나누느냐가 가장 중요하다.
lower bound는 (작은) (크거나 같은)으로 나누었고 upper bound는 (작거나 같은) (큰) 으로 나누었다.
우리가 원하는 값은 ‘같은’에 포함되어 있다!
lower bound는 결국 두 그룹을 나누는 값에서 종료하게 되는데 우리가 원하는 값은 크거나 같은 쪽(end)에 포함되어 있다. start = end + 1에서 종료되기 때문에 start의 값이 우리가 원하는 값이 된다.
upper bound는 start에 값이 된다. 그러나 start는 마지막에 +1이 되어 나오기 때문에 end의 값이 정답이 된다.

 

## 문제 추천

https://www.acmicpc.net/problem/2143

2143번: 두 배열의 합