백준 1920번

원본 : www.acmicpc.net/problem/1920

1920번: 수 찾기

 

풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

	public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws Exception {
		int n = Integer.parseInt(reader.readLine());
		int arrN[] = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		Arrays.sort(arrN);
		int m = Integer.parseInt(reader.readLine());
		int arrM[] = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		for (int i = 0; i < m; i++) {
			if (find(arrM[i], arrN)) {
				writer.write("1\n");
			} else {
				writer.write("0\n");
			}
		}
		writer.flush();
	}
	
	public static boolean find(int num, int arr[]) {
		int startIndex = 0;
		int endIndex = arr.length;
		int midNum = 0;
		
		while (true) {
			midNum = arr[startIndex + ((endIndex - startIndex) / 2)];
			if (midNum == num) {
				return true;
			} else {
				if (endIndex - startIndex == 1) {
					return false;
				} else if (midNum < num) {
					startIndex += (endIndex - startIndex) / 2;		
				} else if (midNum > num) {
					endIndex -= (endIndex - startIndex) / 2;
				}
			}
		}
		
	}

}