이진탐색

문제

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

 

전체 코드

 

#include <iostream>
 
using namespace std;
 
int num[100001];
 
bool bs(int *arr, int start, int end, int target){
  int mid = (start+end)/2;
  if(start > end)
    return false;
  else{
    if(arr[mid] == target)
      return true;
    else{
      if(arr[mid] < target)
        bs(arr,mid+1,end,target);
      else if(arr[mid] > target)
        bs(arr,start,mid-1,target);
    }
  }
}
int main()
{
  int n,q;
  cin >> n >> q;
 
  for(int i=0; i<n; i++)
    cin >> num[i];
  
  for(int i=0; i<q; i++){
    int target;
    cin >> target;
    if(bs(num,0,n,target) == true)
      cout << "YES";
    else
      cout << "NO";
    cout << "\n";
  }
}