JArchive 프로그래밍 일기

문제

수 찾기 백준 1920

"맞았습니다"코드

#include <bits/stdc++.h>
using namespace std;

int n, m, num;
int arr[100010];

void binarySearch(int target){
  int start = 0;
  int end = n-1;
  int mid = 0;

  while(end >= start){
    mid = (start+end)/2;

    if(target == arr[mid]){
      cout << 1 << '\n';
      return;
    }
    else if (arr[mid] < target){
      start = mid+1;
    }
    else{
      end = mid-1;
    }
  }
  cout << 0 << '\n';
  return;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> arr[i];
  }
  sort(arr, arr+n); // 이분탐색을 위해 미리 정렬 
  cin >> m; 
  while(m--){
    cin >> num;
    binarySearch(num);
  }
  return 0;
}

리뷰

이중 for문으로 검사하면 n, m둘다 10만개가 주어질 수 있기 때문에.
시간초과가 난다.
따라서 첫 번째 배열을 정렬 시키고, 두 번째 숫자가 들어올 때마다 이분 탐색시켰다.