[백준] 1920 수 찾기 - BinarySearch / Java

graycode 2023. 1. 28. 15:12

• 문제 링크

1920번: 수 찾기

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들

www.acmicpc.net

• 풀이 과정

• 풀이 코드

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

public class Main {

    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        arr = new int[n];

        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());

        st = new StringTokenizer(br.readLine());
        while (m-- > 0)
            bw.write(binarySearch(Integer.parseInt(st.nextToken())) + "\n");

        bw.flush();
    }

    private static int binarySearch(int key) {
        int low = 0, high = arr.length - 1, mid;

        while (low <= high) {
            mid = (low + high) / 2;

            if (arr[mid] == key)
                return 1;
            else if (arr[mid] > key)
                high = mid - 1;
            else
                low = mid + 1;
        }

        return 0;
    }

}