lower_bound와 upper_bound

1. Lower Bound

lower_bound는 이름에서 알 수 있듯, 하한선을 의미한다. 레퍼런스에 있는 std::lower_bound는 찾고자 하는 value와 같거나 더 큰 값을 찾는다고 되어있다.

Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

즉, value 이상인 값이 처음으로 나오는 위치를 찾는 것이다. 

 

다음은 lower_bound를 구현한 코드이다.

#include <iostream>
using namespace std;

int a[10] = {1, 1, 1, 2, 3, 3, 3, 4, 4, 5};

int lb(int find) {
	int left = 0, right = 10;
	
	while(left < right) {
		int mid = (left + right) / 2;
		
		if(a[mid] < find) left = mid + 1;
		else right = mid;
	}
	
	if(right == 10) return -1;
	return right;
}

int main() {
	int find;
	cin >> find;
	
	cout << lb(find) << "\n";
}

lower_bound는 find 이상인 값을 찾으므로, a[mid]값이 find 미만이라면 a[mid]는 절대 구간에 포함시키면 안 된다. 또한 mid 이하의 인덱스에 해당하는 값은 find 이하이기 때문에 (mid + 1)을 구간의 하한으로 설정해야한다. 따라서 left에 (mid + 1)을 넣는다.

 

a[mid]가 find이상이라면 두가지를 고려해야한다.

1. a[mid] == find

a[mid]가 find와 같다면 lower_bound의 정의에 맞긴하나, 지금 보고있는 a[mid]가 배열에서 가장 처음으로 나오는 값일 수도 아닐 수도 있다. 따라서 구간에 포함시켜야한다.

 

2. a[mid] > find

a[mid]가 find를 초과한 값일 경우도 lower_bound의 정의에 맞다. 하지만 mid 미만의 인덱스에서 find와 같은 값이 나올 수도 아닐 수도 있다. 따라서 구간에 포함시켜야한다.

 

즉, a[mid]가 find 이상인 경우 mid를 구간에 포함시켜야한다. mid보다 큰 인덱스에 해당하는 값들은 2번 설명에서 말했듯, 더 작은 값이 mid 미만의 인덱스에서 나올 수 있다. 따라서 right = mid를 함으로써 구간의 상한으로 설정한다.

 

모든 경우를 처리한 경우 right와 left는 같아진다. while문 조건에 left < right를 넣었기 때문이다. 결국 right에 해당하는 인덱스가 우리가 원하는 값이다.

 

나는 일부러 right를 10으로 초기화 했는데, 이유는 lower_bound 정의에 맞지 않는 값이 인풋으로 들어올 경우를 처리하고 싶었기 때문이다. 정의에 맞지 않는다면, left값이 계속 mid + 1이 되어 right를 초기화 했던 값이 될것이다.

---

2. Upper Bound

upper_bound는 상한선이며, 레퍼런스에 있는 std::upper_bound는 찾고자 하는 value보다 큰 값을 찾는다고 되어있다.

Returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found.

 

즉, value 초과인 값이 처음으로 나오는 위치를 찾는 것이다. 

 

다음은 upper_bound를 구현한 코드이다.

#include <iostream>
using namespace std;

int a[10] = {1, 1, 1, 2, 3, 3, 3, 4, 4, 5};

int ub(int find) {
	int left = 0, right = 10;
	
	while(left < right) {
		int mid = (left + right) / 2;
        
		if(a[mid] <= find) left = mid + 1;
		else right = mid;
	}
	
	return right;
}

int main() {
	int find;
	cin >> find;
	
	cout << ub(find) << "\n";
}

upper_bound는 lower_bound와 한가지만 다르다.

 

a[mid]가 find와 같을 때도 구간에 포함시키지 않는데, 이유는 upper_bound는 find 초과인 값을 찾는 것이 정의이기 때문이다. 따라서 이 부분만 처리해주면 upper_bound를 구현할 수 있다.