[C++] lower_bound(), upper_bound() 함수

1. lower_bound()와 upper_bound()의 소개

lower_bound(하한)와 upper_bound(상한)는 C++의 내장 함수로, 이진 탐색으로 구현이 되어 있습니다. 이진 탐색은  배열이 이미 정렬된 상태에서 적용되므로, 위 함수들을 사용할 때에도 정렬된 상태에서 적용되어야 합니다.

 

lower_bound()와 upper_bound()는 이진 탐색과 같은 시간복잡도 O(log2)를 갖습니다.

 

2. lower_bound()

하한은 특정 값 k보다 같거나 큰 값이 처음 나오는 위치의 주소가 됩니다. 즉, k값 이상인 값이 처음 나오는 곳의 주소를 말합니다.

 

함수의 형태는 다음과 같습니다.

lower_bound(배열의 시작, 배열의 끝, 특정 값 k)

 

 

3. upper_bound()

상한은 특정 값 k보다 큰 값이 처음으로 나오는 위치의 주소가 됩니다. 즉 k값 초과인 값이 맨 처음으로 나오는 곳의 주소를 말합니다.

 

함수의 형태는 다음과 같습니다.

upper_bound(배열의 시작, 배열의 끝, 특정 값 k)

 

 

만약 특정 값을 주어진 배열에서 찾을 수 없는 경우, 배열의 끝을 반환합니다.

4. 찾고자 하는 값(x)이 배열에 존재하지 않는 경우

하한과 상한이 모두 같은 위치를 가리킵니다.

 

1) x 미만인 것과 x 초과인 것이 둘 다 존재하는 경우

하한과 상한이 모두 x 초과인 값이 시작하는 위치를 가리킵니다.

2) x 미만인 것만 존재하는 경우

하한과 상한이 모두 배열의 끝을 가리킵니다.

3) x 초과인 것만 존재하는 경우 

하한과 상한이 모두 배열의 시작을 가리킵니다.

 

만약 인덱스를 얻는 것이 목적이라면, 함수가 리턴한 주소에서 배열의 첫 번째 원소가 가리키는 주소를 빼주어 인덱스를 구할 수 있습니다.

#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;
}

출처: https://codingdog.tistory.com/entry/lowerbound-upperbound-함수-정렬이-되어-있다면-쓸-수-있다 [강아지의 코딩공부]