이진탐색

문제

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

 

// 코드

import java.util.*;
import java.io.*;
 
public class Main{
  
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  static int n, q;
  static int[] arr;
  
  static boolean binarySearch(int start, int end, int value) {
    
    if(start > end) return false; // 기저조건 : 숫자가 하나도 남지 않았을 경우.
    else if(start == end) { // 기저조건 : 숫자가 하나만 남았을 겨우.
      if(arr[start] == value) return true;
      else return false;
    } else {
      
      int mid = (start + end) / 2;
      if(arr[mid] == value) return true;
      else if(arr[mid] > value) return binarySearch(start, mid-1, value);
      else return binarySearch(mid+1, end, value);
      
    }
    
  }
  
  public static void main(String[] args) throws Exception {
 
    // Please Enter Your Code Here
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    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());
    StringBuilder sb = new StringBuilder();
    for(int i=0; i<q; i++) {
      int qNum = Integer.parseInt(st.nextToken());
      boolean getFlag = binarySearch(0, n-1, qNum);
      if(getFlag) sb.append("YES\n");
      else sb.append("NO\n");
    }
    bw.write(sb.toString());
    br.close();
    bw.flush();
    bw.close();
 
  }
}