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

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

10816번: 숫자 카드 2

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

int main(){
	int n, m;
	int arr[500000];
	int ans[500000] = {0};
	
	cin >> n;
	for(int i = 0 ; i < n; i++) scanf("%d", &arr[i]);
	sort(arr,arr+n);
	
	cin >> m;
	for(int i = 0; i < m; i++)scanf("%d", &ans[i]);
	

	
	for(int i = 0;  i < m; i++){
		bool chk = 0;
		int l_tmp = -1,r_tmp = n;
		int left = -1, right = n;

		while(left + 1 < right){
			int mid = (left+right)/2;
			
			if(arr[mid] > ans[i]) right = mid;
			else if(arr[mid] < ans[i])  left = mid;
			if(arr[mid] == ans[i]){
				l_tmp = mid;
				right = mid;
				left = -1;
				chk =true;
			}
		}
		
		left = -1, right = n;
		while(left + 1 < right){
			int mid = (left+right)/2;
			
			if(arr[mid] > ans[i]) right = mid;
			else if(arr[mid] < ans[i])  left = mid;
			if(arr[mid] == ans[i]){
				r_tmp = mid;
				left = mid;
				right = n;
				chk=true;
			}
		}
		if(chk)printf("%d ", r_tmp-l_tmp+1);
		else   printf("0 ");
	}
}