lower_bound(), upper_bound()

lower_bound

찾으려는 key 값과 같거나 더 큰 숫자가 배열의 몇 번째에서 처음 등장하는지 찾을 수 있다. 탐색을 진행할 배열 혹은 벡터는 오름차순으로 정렬되어 있어야 정확한 결과를 보장한다.

배열에서의 활용

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {

	int arr[6] = { 1,2,3,4,5,6 };
	cout << "lower_bound(6) : " << lower_bound(arr, arr + 6, 6) - arr;

    // 결과 -> lower_bound(6) : 5

	return 0;
}

6과 같거나 더 큰 값의 인덱스를 arr에서 탐색하는 예제입니다. 함수는 인덱스를 반환합니다. lower_bound의 반환형은 iterator 이므로 실제로 몇 번째 인덱스인지 알고 싶다면, 위 코드와 같이 lower_bound 값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼 주면 됩니다.

백터에서 활용

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {

	vector<int> arr = { 1,2,3,4,5,6,6,6 };
	cout << "lower_bound(6) : " << lower_bound(arr.begin(), arr.end(), 6) - arr.begin();

    // 결과 -> lower_bound(6) : 5

	return 0;
}

upper_bound

찾으려는 key 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾기위해서 사용한다. 탐색을 진핼할 배열 혹은 벡터는 오름차순으로 정렬되어 있어야 바른 결과가 보장된다.

배열에서의 활용

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {

	vector<int> arr = { 1,2,3,4,5,6 };
	cout << "upper_bound(3) : " << upper_bound(arr.begin(), arr.end(), 3) - arr.begin();

    // 결과 -> upper_bound(3) : 3
	return 0;
}