[백준] 1920번 - 이분 탐색

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
vector<int> ar1, ar2,answer;

int binarySearch(int key) {
	int left = 0;
	int right = n - 1;	
	for (;;) {
		int mid = (left + right) / 2;
		if (ar1[mid] == ar2[key])
			return 1;
		else if (ar1[mid] > ar2[key])
			right = mid - 1;
		else if (ar1[mid] < ar2[key])
			left = mid + 1;
		if (left > right)
			return -1;
	}
}

int main() {	
	cin >> n;	
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		ar1.push_back(a);
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		ar2.push_back(a);
	}
	sort(ar1.begin(),ar1.end());

	for (int i = 0; i < m; i++) {
		if (binarySearch(i) == 1)
			cout << 1 << '\n';
		else if (binarySearch(i) == -1)
			cout << 0 << '\n';
	}	
}

 

이분 탐색을 사용하지 않아도 되는데 카테고리가 이분 탐색이라 억지로 사용했다.(...)

이분 탐색은 오름차순으로 정렬되어 있는 배열에 대해서 key값을 찾는다. 배열의 중간 값을 지정해서 중간 값이 

key보다 크면 중간 값 왼쪽 구간에서 다시 검색하고 key보다 작으면 중간 값 오른쪽 구간에서 검색하는 것을 반복한다.

그래서 구간의 최소값을 나타내는 left가 최대값을 나타내는 right보다 커질 때 까지 값을 못 찾으면 -1을 출력한다.