[c++] lower_bound, upper_bound 함수

lower_bound, upper_bound 란?

c++에서 이진 탐색으로 원소를 탐색하는 기능을 합니다.

 

lower_bound

찾으려는 target 값보다 같거나 큰 숫자 가 배열 몇 번째에서 처음 등장하는지 찾는 함수

 -사용 조건 : 탐색을 진행할 배열 및 벡터는 오름차순으로 정렬되어 있어야 한다.

 

lower_bound 예제

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

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

	vector<int> nums = { 1,3,5,6 };
	int target = 4;

	auto a = lower_bound(nums.begin(), nums.end(), target);
	
	int index = a - nums.begin();

	return 0;
}

▶nums 시작 부터 끝까지 탐색하면서 target 숫자가 처음으로 나오는 위치의 인덱스 번호를 반환하는 예제입니다.

    →nums 벡터에서 target 은 nums[1] , nums[2] 사이의 숫자 입니다.

 

▶ lower_bound의 반환형은 iterator이므로 실제 index를 구하려면 

lower_bound값에서 벡터의 첫번째 주소를 가르키는 주소(iterator)를 빼 주면 됩니다.

 

upper_bound

찾으려는 target 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾는 함수

 - 사용 조건 : 탐색을 진행할 배열 및 벡터는 오름차순으로 정렬되어 있어야 한다.

 

upper_bound 예제

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

	vector<int> nums = { 1,3,5,6 };
	int target = 5;

	auto b = upper_bound(nums.begin(), nums.end(), target);
	int index2 = b - nums.begin();  // = 3

	return 0;
}

▶ 벡터의 처음부터 끝까지 탐색하면서  target 값인 5를 처음으로 초과하는 원소의 index번호를 반환하는 예제입니다. 

  → 5를 처음 초과하는 원소는 6이므로 index = 3, 따라서 결과는 3 입니다.

 

활용 문제

오름차순 정렬된 자료에서 특정 범위에 속하는 숫자들이 몇 개 있는지 탐색하고자 할 때

 

▶이진 탐색 기반의 lower_bound, upper_bound를 사용하면 시간 복잡도를 효과적으로 줄일 수 있습니다.

 

▶예제 : { 1,3,5,5,7,8,8,10,10,11,13}  에서 5이상 11이하의 숫자가 몇 개인지 구하시오

int main() {
	vector<int> arr = { 1,3,5,5,7,8,8,10,10,11,13 };
	int result = upper_bound(arr.begin(), arr.end(), 11) - lower_bound(arr.begin(), arr.end(), 5);

	return 0;
}

 arr 벡터는 오름차순으로 정렬되어 있어야한다.

 5이상 11이하의 수의 개수를 구하기 위해 

 (11을 초과하는 첫번째 원소의 index) - (5 이상인 원소의 첫번째 index) 를 계산하면 된다.

 

오름차순 정렬된 자료에서 특정 숫자가 몇 번 나오는지 탐색하고자 할 때

 

▶이진 탐색 기반의 lower_bound, upper_bound를 사용하면 O(lon N) 으로 탐색 가능하다.

 

▶예제 : { 1,3,5,5,7,8,8,10,10,11,13}  에서 5의 개수를 구하시오

int main() {

	vector<int> arr = { 1,3,5,5,5,8,8,10,10,11,13 };
    int result = upper_bound(arr.begin(), arr.end(), 5) - lower_bound(arr.begin(), arr.end(), 5);

	return 0;
}

 5의 개수를 구하기 위해

 (5를 초과하는 첫번째 원소의 index) - (5 이상인 원소의 첫번째 index)를 계산하면 된다.