1920번: 수 찾기 [JAVA]

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

접근 방식) 이분탐색

1. N개의 정수를 배열에 저장

2. M개 만큼 반복문 돌면서, 해당 정수가 배열에 있는지 확인 (이분탐색)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class B_1920 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] 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);

        int M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());
            boolean isFind = false;
            int left = 0;
            int right = N - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (arr[mid] == num) {
                    isFind = true;
                    break;
                } else if (arr[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            if (isFind)
                sb.append(1).append('\n');
            else
                sb.append(0).append('\n');
        }
        System.out.print(sb);
    }
}