백준 숫자카드

링크

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.*;  
  
class Main {  
  
    static int[] n;  
    public static void main(String args[]) throws IOException{  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
  
        int  N = Integer.parseInt(br.readLine());  
  
        n = new int[N];  
        StringTokenizer st = new StringTokenizer(br.readLine());  
  
        for(int i=0; i< N; i++){  
            n[i] = Integer.parseInt(st.nextToken());  
        }  
        Arrays.sort(n);  
  
        int M = Integer.parseInt(br.readLine());  
        st = new StringTokenizer(br.readLine());  
        for(int i=0; i<M; i++){  
            int x = Integer.parseInt(st.nextToken()) ;  
  
            int answer = find(x);  
            System.out.print(answer + " ");  
        }  
  
    }  
  
    public static int find(int target){  
        int start =0;  
        int end = n.length-1;  
  
        while(start<=end){   //start가 end와 겹치는 지점까지 하지 않으면
        //맨 말단의 값은 체크하지 않게 된다.
        //이거는 target의 값이 end의 값과 같을 때라고 생각하고 손으로
        //써서 풀어보면 이해가 간다!
            int mid = (start + end)/2;  
  
            if(n[mid] < target){  
                start = mid+1;  
            }else if(n[mid] > target){  
                end = mid-1;  
            }else if(n[mid] == target){  
                return 1;  
            }  
        }  
        return 0;  
    }  
  
}

이분탐색을 활용해서 값을 호딱호딱 빨리 찾는 문제
이분탐색을 이용한 탐색은 정렬이 되어있어야한다!

while(start<=end)로 두었는데 여기서 start<=end는 말단의 값일 때 값을 체크할 것이냐 말 것이냐를 확인한다!

REVIEW

이분탐색 기초는 이제 잘 쓰고있네용