[알고리즘] lower_bound, upper_bound

 

사용 전 배열, vector 오름차순 정렬 필요

1. 직접 구현하기

lower_bound

#include<iostream>
using namespace std;

#define MAX_N 500000

int n;
int arr[MAX_N];

//lower_bound(x) : x보다 같거나 큰 수 중에 가장 왼쪽에 있는 수의 인덱스
int lower_bound(int x) {
	int left = 0;
	int right = n - 1;
	int ret = n; // 같거나 큰 최초의 위치를 찾아야 하므로 최악을 고려해서 n이 초깃값이 되어야 함
	while (left <= right) {
		int mid = (left + right) / 2;
		if (arr[mid] >= x) { // mid 값이 관심있는 영역이라면
			ret = mid;
			right = mid - 1; //가장 왼쪽에 있는 수의 인덱스를 찾아야 하니깐, 왼쪽 부분을 살펴봄

		}
		else { //mid 값이 관심있는 영역이 아니라면
			left = mid + 1;
		}
	}
	return ret;
}

 

upper_bound

// upper_bound(x) : x보다 큰 수 중에 가장 왼쪽에 있는 수의 인덱스
int upper_bound(int x) {
	int left = 0;
	int right = n - 1;
	int ret = n; // x보다 큰 최초의 위치를 찾아야 하므로 최악을 고려해서 n이 초깃값이 되어야 함
	while (left <= right) {
		int mid = (left + right) / 2;
		if (arr[mid] > x) { // mid 값이 관심있는 영역이라면
			ret = mid;
			right = mid - 1;  //가장 왼쪽에 있는 수의 인덱스를 찾아야 하니깐, 왼쪽 부분을 살펴봄
		}
		else { //mid 값이 관심있는 영역이 아니라면
			left = mid + 1;
		}
	}
	return ret;
}

 

2. STL 사용하기

STL은 배열이라면 포인터를 리턴하고 vector라면 iterator를 리턴합니다.

 

lower_bound

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

int main(void) {
	vector<int> v({ 1, 2, 3, 3, 3, 6, 7, 8, 9, 10 });
	cout << lower_bound(v.begin(), v.end(), 3) - v.begin() << '\n'; // idx : 2
	return 0;
}

 

upper_bound

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

int main(void) {
	vector<int> v({ 1, 2, 3, 3, 3, 6, 7, 8, 9, 10 });
	cout << upper_bound(v.begin(), v.end(), 3) - v.begin() << '\n'; // idx : 5
	return 0;
}