Lower bound & Upper bound

개요

이분 탐색문제를 풀이하다 나온 개념

---

특징

이분 탐색을 응용한 알고리즘으로

정렬된 수열에서 찾고자 하는 값들의의 첫인덱스, 마지막 인덱스 + 1 을 구할 수 있다.

---

왜 사용하는가?

경험상 적절한 위치를 알기 위해서 사용하는 것 같다.

Lower bound는 찾고자 하는 값 이상의 부분수열에서 첫번째 인덱스

Upper bound는 찾고자 하는 값을 초과하는 부분수열에 첫번째 인덱스

 

이 위치들의 특징은 이곳에 찾고자 하는 값을 삽입해도 오름차순이 유지되는 특징이있다.

그리고 Upper bound -  Lower bound 의 값은 그 안에 속한 원소의 개수도 구할 수 있다.

---

구현

---

Lower bound

int Lower_bound(const int * arr, const int & size, const int & f)
{
	int s = 0, e = size, m;
	while (s < e)
	{
		m = (s + e) / 2;

		if (f <= arr[m]) e = m;
		else s = m + 1;
	}

	return s;
}

Lower bound는 f 가 시작 되는 지점을 찾는게 목표이다.

고로

시작지점은 arr[s] <= f, 끝 지점은 f <= arr[e] 라는 조건이 붙는다.

 

f <= arr[m] 일때 이 조건과 같은 e를 m에 두고 

나머지 경우인 arr[m] < f 는 해당되는 s를 m의 위치에 두되,

그냥 두면 s가 f에 도달하지 못하므로 m + 1인 인덱스를 s에 부여해준다.

---

Upper bound

int Upper_bound(const int * arr, const int & size, const int & f)
{
	int s = 0, e = size, m;
	while (s < e)
	{
		m = (s + e) / 2;

		if (f < arr[m]) e = m;
		else s = m + 1;
	}

	return e;
}

Upper bound는 f 가 끝나는 지점 + 1 을 찾는게 목표이다.

고로

시작지점은 arr[s] <= f, 끝 지점은 f < arr[e] 라는 조건이 붙는다.

 

f < arr[m] 일때 이 조건과 같은 e를 m에 둔다면 f와 arr[e]는 같은 값이 될수 없으며

나머지 경우인 arr[m] <= f 는 위으 Lower bound와 같다.

---