upper_bound & lower_bound

 

 

탐색 알고리즘 중 하나인 이분탐색은

찾고자 하는 값이 없으면 탐색에 실패해버리고 만다.

 

하지만 탐색에 실패하지 않도록 보완해준 알고리즘들이 있다.

바로, lower_bound 와 upper_bound 이다.

 

이 둘 모두 이분탐색을 기반으로 하기 때문에 데이터는 오름차순으로 정렬되어 있어야만 한다.

---

lower_bound

찾고자하는 값보다 크거나 같은 값 중 가장 왼쪽 값의 위치를 반환한다.

즉, 찾고자하는 값 이상이 처음으로 나타나는 위치를 반환한다.

 

만약, lower_bound(10) 이라고 한다면

데이터 중에서 10 이상의 값이 처음 나타나는 곳을 반환하는 것이다.

 

 

위 그림과 같은 데이터가 있을 때 lower_bound(10)은 어떤 값을 반환할까 ?

 

 

찾고자하는 값 10 이상이 처음으로 나타나는 곳은 빨간 박스부분이다.

그러므로 lower_bound(10) = 4 를 반환하게 된다.

 

그렇다면, 찾고자 하는 값이 정확하게 없을 때는 어떻게 될까 ?

 

 

위 그림에서 lower_bound(10) 은 무엇을 반환할까 ?

10 이상의 값이 처음으로 나오는 곳이라는 개념을 잘 생각해보자.

 

 

이번에도 역시 10이상의 값이 처음 나오는 곳은 4번째 위치이다.

 

매우 쉽다.

 

이렇게 개념은 무척이나 간단하다.

그렇다면 코드로는 어떻게 될까 ?

 

int lower_bound(int left,int right,int tar)
{
	// left : 배열 시작
    // right : 배열 끝
	while (left < right)
    {
		int mid = (left + right)/2;
		if (arr[mid] < tar) left = mid + 1
		else right = mid
	}
	return right;
 }

 

 

아주 간단하게도 기존 이분탐색에서 큰 차이가 없다.

다만, l = m + 1 처럼 r = m - 1 이 기본이었는데 r = m 으로 바뀐다는 점과 반환 값에 주의하자.

 

---

upper_bound

찾고자하는 값보다 큰 값 중 가장 왼쪽 값의 위치를 반환한다.

즉, 찾고자하는 값 초과가 처음으로 나타나는 위치를 반환한다.

 

만약, upper_bound(10) 이라고 한다면

데이터 중에서 10 초과의 값이 처음 나타나는 곳을 반환하는 것이다.

 

이번에도 그림을 통해서 설명해보겠다.

 

위 데이터를 가진 배열에서 upper_bound(10)은 어떤 값을 반환할까 ?

upper_bound는 lower_bound와 달리 찾고자 하는 값을 포함하지 않는다.

그러므로 10을 넘어서는 최초의 값의 위치를 반환할 것이다.

 

 

찾고자하는 값 10 초과 값이 처음으로 나타나는 곳은 빨간 박스부분이다.

그러므로 upper_bound(10) = 5 를 반환하게 된다.

 

그렇다면 이번에도 찾고자 하는 값이 정확하게 없을 때는 어떻게 될까 ?

 

 

위와 같은 데이터에는 역시 10은 없다.

하지만, 찾고자 하는 값 초과를 반환하는 upper_bound라면  ?

 

 

이번에는12가 10보다 큰 가장 최초의 값이 되기 때문에

upper_bound(10) = 4 를 반환하게 된다.

 

이 개념 역시 너무 쉽지 않은가 ?

이번에도 코드로 한번 보자.

 

int upper_bound(int left,int right,int tar)
{
	// left : 배열 시작
    // right : 배열 끝
	while (left < right)
    {
		int mid = (left + right)/2;
		if (arr[mid] <= tar) left = mid + 1
		else right = mid
	}
	return right;
 }

 

반환값부터 left, right 값 변경 부분까지 똑같다.

그래서 처음 보면 뭐가 다른지 모를수도 있는데

중간에 비교하는 부분이 다르다.

 

lower_bound는 arr[mid] < tar

upper_bound는 arr[mid] <= tar

 

 

코드를 천천히 따라가보면서 그림을 그려보면 이해가 될 것이다.

적절한 예시가 있어 링크로 남긴다.

 

https://yoongrammer.tistory.com/105

Lower bound & Upper bound 개념 및 구현

 

참고로 C++의 경우 algorithm 헤더에서 이 둘을 지원한다.

map, set, array 등에서 사용할 수 있는데

차후 문제 풀이에서 사용하게 되면 문제와 함께 다시 쓰도록 하겠다.

 

 

참고로 만약 찾고자하는 값이 30이라면

lower_bound든 upper_bound든 모두 값을 찾을 수 없게된다.

이 경우에는 마지막 포인터를 반환하면서 값이 존재하지 않음을 알린다.

주로 end()로 표현될 수 있음에 주의하면서 사용하자.