Lower Bound & Upper Bound

Lower Bound & Upper Bound은 이분 탐색에서 파생된 알고리즘으로 

 

Lower Bound는 "찾는 값 T 이상이 처음 나오는 위치를 찾는" 알고리즘이고,

Upper Bound는 "찾는 값 T 초과한 값이 처음 나오는 위치를 찾는" 알고리즘이고,

Lower Bound

알고리즘 자체는 이분 탐색과 매우 유사하다.

 

중간 값이 작으면 시작 위치를 중간 다음 위치로, 크거나 같으면 끝 위치를 중간 위치로 이동시킨다.

 

이분 탐색과는 다르게 끝 위치를 중간 이전 위치가 아닌 중간 위치로 움직인다.

 

간단하게 생각해보면 값이 작다는 건 중간 위치까지는 원하는 값 이상이 절대 없기에 다음 위치로 이동시키지만,

 

크거나 같다면 중간 위치의 값이 찾는 값 이상인 처음 위치일 수도 있기에 중간 위치로 설정한다.

#include <stdio.h>

#define N 10

int lower_bound(int[], int, int);

int main()
{
	int a[N] = { 3, 5, 48, 73, 94, 129 ,150, 279, 307, 500 };
	int T = 179;

	printf("lower bound is arr[%d]\n", lower_bound(a, T, N));
	return 0;
}

int lower_bound(int arr[], int target, int size)
{
	int mid, l, r;
	l = 0, r = size - 1;

	while (r > l)
	{
		mid = (l + r) / 2;
		if (arr[mid] >= target) 
			r = mid;
		else l = mid + 1;
	}
	return r;
}

 

Upper Bound

Upper Bound는 Lower Bound와 매우 유사하다.

 

Lower Bound에서 "크거나 같다"를 "크다"로 바꿔주면 된다.

#include <stdio.h>

#define N 10

int upper_bound(int[], int, int);

int main()
{
	int a[N] = { 3, 5, 48, 73, 94, 129 ,150, 279, 307, 500 };
	int T = 279;

	printf("lower bound is arr[%d]\n", upper_bound(a, T, N));
	return 0;
}

int upper_bound(int arr[], int target, int size)
{
	int mid, l, r;
	l = 0, r = size - 1;

	while (r > l)
	{
		mid = (l + r) / 2;
		if (arr[mid] > target) 
			r = mid;
		else l = mid + 1;
	}
	return r;
}