[백준] 1920. 수 찾기 <C++>

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

이 문제는 시간초과를 위한 문제이다.

 

퀵정렬을 이용해 정렬하고, 이분탐색으로 풀어야한다.

 

그리고 C++언어를 이용해 cin, cout을 이용해도 시간초과가 발생하기 때문에

cin, cout의 시간을 줄여줄 명령어도 사용해주어야한다.

 

 

//cin, cout의 시간을 줄여주는 명령어

  cin.tie(NULL);
  ios_base::sync_with_stdio(0);

 

 

//이분탐색을 해주는 함수

bool Bin_search(int n, int num){
  int left=0, right=n-1;
  int mid;

  while(left<=right)
  {
    mid=(left+right)/2;

    if(arr[mid]>num) right=mid-1;
    else if(arr[mid]<num) left=mid+1;
    else return 1;
  }

  return 0;
}

 

 

//전체 코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[100001];

bool Bin_search(int n, int num){
  int left=0, right=n-1;
  int mid;

  while(left<=right)
  {
    mid=(left+right)/2;

    if(arr[mid]>num) right=mid-1;
    else if(arr[mid]<num) left=mid+1;
    else return 1;
  }

  return 0;
}

int main() {
  int n, m, input;
  
  cin.tie(NULL);
  ios_base::sync_with_stdio(0);
  
  cin>>n;
  for(int i=0; i<n; i++)
    cin>>arr[i];

  sort(arr,arr+n);

  cin>>m;
  for(int i=0; i<m; i++){
    cin>>input;
    cout<<Bin_search(n, input)<<'\n';
  }
}