[실전 문제] 이진탐색

1. 문제

n개의 오름차순으로 정렬된 숫자가 주어지고, 그 후 q개의 질문이 주어진다. 각각의 질문은 특정 숫자가 n개의 숫자 내에 존재하는지를 판별하는 것이다. 모든 q개의 질문에 대하여 답을 하는 프로그램을 작성하시오. 

---

입력

첫 번째 줄에 숫자의 개수 n, 그리고 질문의 개수 q가 주어진다 ( 1 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000) 이는 오름차순으로 정렬되어 주어진다. 두 번째 줄에 n개의 숫자가 주어진다. 세 번째 줄에 q개의 질문이 주어진다. 각 수는 21억보다 작은 정수다. 

출력

각 질문에 대하여 숫자가 존재하면 YES, 아니면 NO를 한 줄에 하나씩 출력한다.

예제 입력

10 4
1 2 4 8 10 11 12 14 15 19
4 5 8 17

예제 출력

YES
NO
YES
NO

 

 

 

2. 풀이

이진 탐색은 정렬되어있는 배열에서 중간값을 이용하여 찾고자 하는 값을 찾을 때 사용하는 빠른 탐색기법이다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int n;
    private static int q;
    private static int[] arr;

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        q = Integer.parseInt(st.nextToken());

        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < q; i++) {
            int value = Integer.parseInt(st.nextToken());
            if(binaySearch(0, n-1, value)) bw.write("YES\n");
            else bw.write("NO\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }

    private static boolean binaySearch(int s, int e, int value) {

        if(s > e) return false;
        if(s == e) {
            if(arr[s] == value) return true;
            else return false;
        } else {
            int mid = (s+e)/2;
            if(arr[mid] < value) return binaySearch(mid+1, e, value);
            else if(arr[mid] > value) return binaySearch(s, mid-1, value);
            else return true;
        }
    }
}