[C++] binary_search, lower_bound, upper_bound

binary_search, lower_bound, upper_bound

정렬되어 있는 배열, 컨테이너 등을 대상으로 탐색한다.

• binary_search: 탐색 대상이 되는 값이 존재하는지 확인하고 들어 있다면 true, 없다면 false를 반환한다.
• lower_bound: 찾고자 하는 값 이상이 처음 나타나는 위치를 반환한다.
• upper_bound: 찾고자 하는 값을 초과하는 값이 처음 나타나는 위치를 반환한다.

 

 

lower_bound, upper_bound

 

문제

 

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

12015번: 가장 긴 증가하는 부분 수열 2

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

int main(void)
{
	int N;
	cin >> N;

	vector<int> v;
	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;

		auto iter = lower_bound(v.begin(), v.end(), n);
		if (iter == v.end())
			v.push_back(n);
		else
			*iter = n;
	}
	cout << v.size();
}

 

문제 : 찾고자 하는 값의 개수 구하기

 

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

10816번: 숫자 카드 2

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

int num[500001];

int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
		cin >> num[i];

	sort(num, num + N);

	int M, tmp;
	cin >> M;
	for (int i = 0; i < M; ++i) {
		cin >> tmp;
		cout << upper_bound(num, num + N, tmp) - lower_bound(num, num + N, tmp) << " "; // 개수 구하기
	}
}

 

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

7453번: 합이 0인 네 정수

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	vector<int> A(n), B(n), C(n), D(n);
	for (int i = 0; i < n; i++)
		cin >> A[i] >> B[i] >> C[i] >> D[i];

	vector<int> sumA, sumB;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			sumA.push_back(A[i] + B[j]);
			sumB.push_back(C[i] + D[j]);
		}

	sort(sumA.begin(), sumA.end());
	sort(sumB.begin(), sumB.end());

	long long ans = 0;
	for (int i = 0; i < sumA.size(); i++)
		ans += upper_bound(sumB.begin(), sumB.end(), -sumA[i]) - lower_bound(sumB.begin(), sumB.end(), -sumA[i]);
	cout << ans;
	return 0;
}