[C에서 C++로 넘어가기] - 7. 이진 탐색- binary_search(), upper_bound(), lower_bound()

C++에서 이진 탐색을 이용한 3가지 편리한 함수를 소개하겠습니다.

 

먼저 간단히 소개를 드리자면,

 

binary_search(first, last, value)는

주어진 범위에서 value값이 존재하면 1, 존재하지 않으면 0을 반환하는 함수입니다.

 

lower_bound(first, last, value)는 

주어진 범위에서 value값 보다 크거나 같은 첫 번째 원소의 주소를 반환하는 함수입니다.

만약 그러한 원소가 없다면 end값을 리턴합니다.

upper_bound(first, last, value)는

주어진 범위에서 처음으로 value값을 초과하는 원소의 주소를 반환하는 함수입니다.
만약 그러한 원소가 없다면 end값을 리턴합니다.

 

 

위의 3가지 함수는 <algorithm> 헤더파일을 추가한 다음 사용할 수 있습니다.
또한, 이진 탐색을 이용하므로 O(nlogn)의 시간 복잡도를 가지며, 정렬된 리스트에서 사용이 가능합니다.

 

---

binary_search() 함수 사용 예

 

binary_search()함수의 사용 예시를 보기 위해 이진탐색을 이용한 문제를 살펴보겠습니다.

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

이진탐색으로 리스트에 어떤 숫자가 포함되어 있는지 확인하는 문제입니다.

binary_search() 함수를 사용하지 않고 위 문제를 풀이하면 다음과 같습니다.

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

void rFindElement(vector<int>& L, int k, int start, int end) {
	if (start > end) {		// base case
		cout << "0 ";
		return;				// k가 없는 경우
	}
	int mid = (start + end) / 2;
	if (L[mid] == k) {
		cout << "1 ";		// k를 찾은 경우
		return;
	}
	else if (L[mid] > k) {
		return rFindElement(L, k, start, mid - 1);
	}
	else {
		return rFindElement(L, k, mid + 1, end);
	}
}
void findElement(vector<int>& L, int k, int n) {
	return rFindElement(L, k, 0, n - 1);
}

int main() {

	cin.tie(NULL);
	ios::sync_with_stdio(false);

	vector<int> v1;
	int n, m, tmp;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v1.push_back(tmp);
	}

	sort(v1.begin(), v1.end());
    
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> tmp; 
		findElement(v1, tmp, n);
	}

	return 0;
}

이진탐색을 구현하는 함수를 따로 만들어서 풀이해 봤습니다. 

하지만 binary_search() 함수를 이용하면 굳이 따로 함수를 구현하지 않아도 다음과 같이 풀 수 있습니다.

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

int main() {

	cin.tie(NULL);
	ios::sync_with_stdio(false);

	vector<int> v1;
	int n, m, tmp;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v1.push_back(tmp);
	}

	sort(v1.begin(), v1.end());

	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> tmp;
		cout << binary_search(v1.begin(), v1.end(), tmp) << " ";
	}

	return 0;
}

위와 같이 훨씬 간단하게 문제를 해결할 수 있습니다.

 

---

lower_bound(), upper_bound() 사용 예

 

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

리스트 안에 특정 숫자가 몇개 있는지 물어보는 문제입니다.

lower_bound(), upper_bound()를 이용하면 다음과 같이 풀이가 가능합니다.

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

int main() {

	cin.tie(NULL);
	ios::sync_with_stdio(false);

	vector<int> v1;
	int n, m, tmp;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v1.push_back(tmp);
	}

	sort(v1.begin(), v1.end());

	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> tmp;
		int upper = upper_bound(v1.begin(), v1.end(), tmp) - v1.begin();
		int lower = lower_bound(v1.begin(), v1.end(), tmp) - v1.begin();
		cout << upper - lower << " ";
	}

	return 0;
}