[C++] lower_bound, upper_bound

STL의 lower_bound, upper_bound는 이분탐색을 이용하여 특정 원소를 찾는 탐색 알고리즘임.

올바를 결과를 얻기 위해서 함수를 적용할 배열은 반드시 오름차순 정렬되어 있어야 하며 <algorithm> 헤더파일에 포함됨.

 

lower_bound

- 찾으려는 key값이 최초로 나타나는 지점의 인덱스를 리턴.

- 배열에 해당 key값이 없다면, key값보다 큰 원소가 최초로 나타나는 지점의 인덱스를 리턴.

- 즉, key값 이상의 원소가 최초로 나타나는 지점의 인덱스를 리턴하는 함수임.

 

upper_bound

- 찾으려는 key값보다 큰 원소가 최초로 나타나는 지점의 인덱스를 리턴. 

 

1) lower_bound, upper_bound 구현

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

int arr[10] = { 1, 1, 2, 2, 6, 6, 8, 8, 8, 9 };

int lowerBound(int start, int end, int item) {
	while (start < end) {
		int mid = (start + end) / 2;
		if (arr[mid] < item) start = mid + 1;
		else end = mid;
	}
	return end;
}

int upperBound(int start, int end, int item) {
	while (start < end) {
		int mid = (start + end) / 2;
		if (arr[mid] <= item) start = mid + 1;
		else end = mid;
	}
	return end;
}

int main() {
	cout << "lower_bound(6): " << lowerBound(0, 10, 6) << endl;
	cout << "uppser_bound(6): " << upperBound(0, 10, 6) << endl;

	cout << "lower_bound(9): " << lowerBound(0, 10, 9) << endl;
	cout << "uppser_bound(9): " << upperBound(0, 10, 9) << endl;

	return 0;
}