boj 1920 수 찾기

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

1920번: 수 찾기

가장 기본적인 이분탐색 알고리즘으로 해결 가능한 문제입니다.

 

주의할 점은 처음에 주어지는 배열의 크기인 N과

수가 배열안에 존재하는지 확인하는 배열의 크기인 M

둘의 크기가 다르다는 것입니다..

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[];
    static int ques[];
    static int N, M;
 
    static int binarysearch(int l, int r, int x) {
        if (l > r)
            return 0;
 
        int m = (l + r) / 2;
        if (list[m] == x)
            return 1;
        else {
            if (list[m] > x)
                return binarysearch(l, m - 1, x);
            else
                return binarysearch(m + 1, r, x);
        }
    }
 
    static void func() {
        for (int i = 1; i <= M; i++) {
            System.out.println(binarysearch(1, N, ques[i]));
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list);
 
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        ques = new int[M + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= M; i++) {
            ques[i] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}