[Algorithm] 이진탐색

문제

---

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

우선 input 값을 보니, 그냥 단순 탐색을 할 경우, 시간 초과가 뜰 수 있다는 것을 알 수 있다.

그래서 이분탐색을 활용하여 풀어보자

<코드>

#include <stdio.h>

int binarySearch(int arr[], int start, int end, int target){

  if(start>end) return -1;

  else if(start==end){

    if(arr[start] == target) return start;

    else return -1;

  }else{

    int mid = (start + end) / 2;

    if(arr[mid] == target) return mid;

    else if(arr[mid] > target) binarySearch(arr,start,mid-1,target);

    else if(arr[mid] < target) binarySearch(arr,mid+1,end,target);

  }

  

  

}

int main() {

  //Please Enter Your Code Here

  int n,q;

  int arr[100010];

  int target[100010];

  scanf("%d %d",&n,&q);

  for(int i=0; i<n; i++){

    scanf("%d",&arr[i]);

  }

  

  for(int i=0; i<q; i++){

    scanf("%d",&target[i]);

  }

  

  for(int i=0; i<q; i++){

    int inx = binarySearch(arr,0,n-1,target[i]);

    if(inx==-1) {

      printf("NO\n");

    }else{

      printf("YES\n");

    }

  }

  

  return 0;

}