[백준] 10816번 숫자카드2 (이분 탐색)

-문제

 

-코드

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

vector<int> a;
int LBound(int n)
{
	int lt=0, rt=a.size()-1, mid, res=-1;
	while (lt <= rt)
	{
		mid = (lt + rt) / 2;
		if (a[mid] == n)
		{
			res = mid;
			rt = mid - 1;
		}
		else if (a[mid] < n) lt = mid + 1;
		else rt = mid - 1;
	}
	return res;
}

int UBound(int n)
{
	int lt = 0, rt = a.size() - 1, mid, res=-1;
	while (lt <= rt)
	{
		mid = (lt + rt) / 2;
		if (a[mid] == n)
		{
			res = mid;
			lt = mid + 1;
		}
		else if (a[mid] < n) lt = mid + 1;
		else rt = mid - 1;
	}
	return res;
}
int main() 
{
	int tmp, n, m, key, first, last, cnt;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &tmp);
		a.push_back(tmp);
	}

	sort(a.begin(), a.end());
	scanf("%d", &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &key);
		first = LBound(key);
		last = UBound(key);
		if (first == -1 && last == -1) printf("%d ", 0);
		else printf("%d ", last - first + 1);
	}

	return 0;
}