이분탐색 (Binary Search)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	/*
	 * https://www.acmicpc.net/problem/1920
	 */
	public static void main(String[] args) throws IOException {
		
		/*
		 * 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 
		 * 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 
		 * 다음 줄에는 M(1≤M≤100,000)이 주어진다. 
		 * 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 
		 * 모든 정수들의 범위는 int 로 한다.
		 */
		
		/*
		 * 1. A배열 정렬
		 * 2. 이분탐색
		 */
		
		//System.setIn(new FileInputStream("res/algo1/B.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer ST = new StringTokenizer(br.readLine());
		int[] A = new int[N+1];
		for (int i = 1; i <= N; i++){
			A[i] = Integer.parseInt(ST.nextToken());
		}
		
		int M = Integer.parseInt(br.readLine());
		
		ST = new StringTokenizer(br.readLine());
		int[] B = new int[M+1];
		for (int i = 1; i <= M; i++){
			B[i] = Integer.parseInt(ST.nextToken());
		}
		
		Arrays.sort(A);
		for (int i = 1; i <= M; i++){
			int low = 1;
			int hi = N;
			while(low <= hi){
				int mid = (low + hi) / 2;
				if (A[mid] < B[i]){
					low = mid + 1;
				} else if (A[mid] > B[i]){
					hi = mid - 1;
				} else {
					bw.write("1\n");
					break;
				}
			}
			if (low > hi){
				bw.write("0\n");
			}			
		}
		br.close();
		bw.flush();
		bw.close();

	}

}