백준 1920 수 찾기 [C++]

감성적인 개발자 2021. 8. 5. 00:51

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

1920번: 수 찾기

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들

www.acmicpc.net

코드

#include<iostream>
#include<algorithm>

using namespace std;

void BinaryExist(int *arr, int low, int high, int findValue){
    if (low > high){
        cout << "0\n";
        return;
    }
    else{
        int mid = (low + high) / 2;
        if (findValue > arr[mid])
            return BinaryExist(arr, mid+1, high, findValue);
        else if (findValue < arr[mid])
            return BinaryExist(arr, 0, mid-1, findValue);
        else{
            cout << "1\n";
            return;
        }
    }
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int n,m;
  cin >> m;
  int marr[100001];
  for(int i = 0; i < m; i++){
    cin >> marr[i];
  }

  sort(marr, marr + m);

  cin >> n;
  int narr[100001];
  for(int i = 0; i < n; i++){
    cin >> narr[i];
  }

  for (int i = 0; i < n; i++)
    BinaryExist(marr, 0, m - 1, narr[i]);
}

최대 원소 갯수가 100,000 이기 때문에 탐색 시 시간복잡도가 N^2이 되어선 안된다.