[백준 1920] 수 찾기

 

n 배열을 오름차순으로 정렬하고 이분탐색으로 구현했다.

 

1. low, high는 각각 n배열의 최솟값, 최댓값으로 정했다.

2. mid 위치의 값과 현재 선택한 m 배열의 값을 비교하여 low, high 를 바꿔준다.

 

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int a[] = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
            a[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(a);
        
        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int b[] = new int[m];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++)
            b[i] = Integer.parseInt(st.nextToken());
        
        for(int i=0; i<m; i++) {
            int low = 0;
            int high = n;
            while(low + 1 < high) {
                int mid = (low + high)/2;
                if(b[i] > a[mid])
                    low = mid;
                else if(b[i] < a[mid])
                    high = mid;
                else {
                    low = mid;
                    break;
                }
            }
            bw.write(a[low] == b[i] ? 1 + "\n" : 0 + "\n");
        }
        bw.flush();
    }
}