[C++] STL lower_bound, upper_bound 사용법과 예제코드

 

lower_bound함수와 upper_bound함수를 사용하기 위해서는 algorithm 헤더 파일 include 해야 하며, 정렬되어있는 배열 내에서 특정 값을 초과하는 값이 첫 번째로 나오는 인덱스를 찾아낼 때 사용됩니다. 이분 탐색으로 찾아내기 때문에 시간 복잡도는 O(logN)입니다.

 

 

lower_bound(arr, arr+N, value)

배열에서 범위 내의 원소들 중 value값 보다 크거나 같은 첫 번째 원소의 주소를 리턴합니다.
만약 그러한 원소가 없다면 end값을 리턴합니다.

 

upper_bound(arr, arr+N, value)

배열에서 처음으로 value값을 초과하는 원소의 주소를 반환합니다.
만약 그러한 원소가 없다면 end값을 리턴합니다.

 

 

사용법

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

int main()
{
	int arr[11] = { 0,1,2,3,4,5,5,5,5,6,7 };
	
	cout << lower_bound(arr, arr + 11, 5) << endl;
	cout << upper_bound(arr, arr + 11, 5) << endl;
}

lower_bound함수와 upper_bound함수를 출력해보니 각각의 함수가 찾아낸 위치의 주소를 리턴합니다. 만약 인덱스를 얻는 것이 목적이라면 아래의 코드와 같이 사용하면 되겠습니다.

 

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

int main()
{
	int arr[11] = { 0,1,2,3,4,5,5,5,5,6,7 };
	
	cout << lower_bound(arr, arr + 11, 5) - arr << endl;
	cout << upper_bound(arr, arr + 11, 5) - arr << endl;
}

함수가 리턴한 주소에서 배열의 첫 번째 원소가 가리키는 주소를 빼주어 인덱스를 구할 수 있습니다.

 

 

 

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

int main()
{
	int arr[11] = { 0,1,2,3,4,5,5,5,5,6,7 };
	
	cout << lower_bound(arr, arr + 11, 10) << endl;
	cout << upper_bound(arr, arr + 11, 10) << endl;
}

이번에는 arr배열의 최댓값(7) 보다 큰 값을 주었을 때 어떠한 값을 리턴하는지 보니 배열의 [end+1]의 인덱스를 리턴하는 것을 알 수 있었습니다.