[C++]이분 탐색 lower_bound & upper_bound 사용하기

 

 c++ STL에는 이진 탐색을 기반으로 원소를 탐색하는 함수 std::lower_bound, std::upper_bound를 제공합니다. 

 

 이 함수들은 이진 탐색을 기반으로 하기 때문에 해당 배열이 오름차순 정렬 되어 있어야 하며, 시간 복잡도를 효율적으로 줄일 수 있습니다. O(log N)

 

 이 함수들은 오름차순 정렬된 자료에서 특정 범위에 속하는 숫자들이 몇 개 있는지 탐색하고자 할 때 유용합니다!

 

 

 

[ 헤더 ]

 

#include<algorithm>

 

 

 

 

[ lower_bound ]

 

 lower_bound() 함수는 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 그 iterator를 반환합니다. 

 

기본형

std::lower_bound(iterator_First, iterator_Last, key)

 

 iterator를 반환하기 때문에 배열의 해당 위치에 포인터를 반환합니다. 

 

 때문에 해당 위치의 index를 얻으려면 배열의 시작 위치를 빼줘야 합니다. 

 

 

#include<iostream>
#include<algorithm>

using namespace std;

int main(void) {

	int arr[10] = { 10, 6, 3, 2, -1, 10, 10, 8, 5, 3 };

	// 오름차순 정렬
	sort(arr, arr + 10);

	for (int i = 0; i < 10; i++)
		cout << arr[i] << " ";
	cout << endl;

	int x = 10;

	auto lower_it = lower_bound(arr, arr + 10, x);
	auto lower_index = lower_bound(arr, arr + 10, x) - arr;

	cout << lower_it << endl;
	cout << *lower_it << endl;
	cout << lower_index << endl;
	cout << arr[lower_index] << endl;

	return 0;
}

 

 

 

 

 

[ upper_bound ]

 

 upper_bound()는 찾으려는 key 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 그 iterator를 반환합니다. 

 

기본형

std::upper_bound(iterator_First, iterator_Last, key)

 

#include<iostream>
#include<algorithm>

using namespace std;

int main(void) {

	int arr[10] = { 10, 6, 3, 2, -1, 10, 10, 8, 5, 3 };

	// 오름차순 정렬
	sort(arr, arr + 10);

	for (int i = 0; i < 10; i++)
		cout << arr[i] << " ";
	cout << endl;

	int x = 3;

	auto upper_it = upper_bound(arr, arr + 10, x);
	auto upper_index = upper_bound(arr, arr + 10, x) - arr;

	cout << upper_it << endl;
	cout << *upper_it << endl;
	cout << upper_index << endl;
	cout << arr[upper_index] << endl;

	return 0;
}