[백준] 10815번 : 숫자 카드

10815번: 숫자 카드

---

[이진 탐색, Binary Search]

그래프 문제를 주로 풀다가 문제의 스펙트럼을 좀 넓혀보고자 이진 탐색 문제를 풀기로 하였다. 이진 탐색의 기본적인 내용을 다루며 응용에 힘쓰도록 한다.

 

이 문제는 교과서적인 이진 탐색을 물어보는 문제이고, m개의 데이터에 대해 이진 탐색을 수행하면 되므로 딱히 어려울 것은 없어보인다.

# Code </>

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

public class Main {

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

        int[] num = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
            num[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(num);

        int m = Integer.parseInt(br.readLine());
        boolean[] result = new boolean[m];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++) {
            int target = Integer.parseInt(st.nextToken());

            int left = 0, right = n-1;
            while(left <= right){

                int mid = (left + right) / 2;

                if(num[mid] >= target) {
                    if (num[mid] == target)
                        result[i] = true;

                    right = mid - 1;
                }
                else
                    left = mid + 1;
            }
            System.out.print(result[i]?"1 " : "0 ");
        }
    }
}