숫자박스

문제

숫자박스에는 자연수들이 적혀있는 종이들이 N장 들어있다. 숫자 M개가 주어졌을 때, 이 숫자가 적혀있는 숫자가 상자 안에 있는지 아닌지를 구하는 프로그램을 작성하시오.  

입력

첫째 줄에 윤성이가 가지고 있는 숫자 정보의 개수 N (1 ≤ N ≤ 300,000)이가 주어진다. 둘째 줄에는 숫자 정보들이 주어진다. 숫자는 절댓값 1,000,000 이하의 정수이다. 두 숫자 카드에 같은 숫자가 적혀있는 경우는 없다.

셋째 줄에는 M (1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 윤성이가 숫자 박스에 있는지 아닌지를 구해야 할 M개의 숫자가 주어지며, 이 숫자는 공백으로 구분되어져 있다. 이숫자도 1,000,000이하의 정수이다.  

출력

첫째 줄에 입력으로 주어진 M개의 숫자에 대해서, 각 숫자가 숫자 상자안에 있으면 1, 아니면 0을 개행으로 구분해 출력한다.

 

예제 입력

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력

1
0
0
1
1
0
0
1

 

// 코드

import java.util.*;
import java.io.*;
 
public class Main{
  
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  static int n, m;
  static int[] arr;
  
  public static void main(String[] args) throws Exception {
 
    // Please Enter Your Code Here
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    arr = new int[n];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for(int i=0; i<n; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }
    
    Arrays.sort(arr);
    
    StringBuilder sb = new StringBuilder();
    m  = Integer.parseInt(br.readLine());
    st = new StringTokenizer(br.readLine());
    for(int i=0; i<m; i++) {
      int num = Integer.parseInt(st.nextToken());
      boolean resFlag = binarySearch(0, n-1, num);
      if(resFlag) sb.append("1\n");
      else sb.append("0\n");
    }
    
    bw.write(sb.toString());
    br.close();
    bw.flush();
    bw.close();
  }
  
  static boolean binarySearch(int start, int end, int value) {
    
    if(start > end) return false; // 기저조건 : 숫자가 하나도 남아있지 않은 경우.
    else if(start == end) { // 기저조건 : 숫자가 하나만 남아있는 경우.
      if(arr[start] == value) return true;
      else return false;
    } else {
      
      int mid = (start + end) / 2;
      if(arr[mid] == value) return true;
      else if(arr[mid] > value) return binarySearch(start, mid-1, value);
      else return binarySearch(mid+1, end, value);
      
    }
    
  }
  
  
}