1920번 숫자 찾기

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

불러오는 중입니다...

 

단순 배열 2개를 만들어서 무작정 찾으려하니 '시간초과'가 발생하였다.

이진탐색을 이용하여 탐색하였다.

 

시간복잡도를 O(logn)으로 줄인다.

c++의 vector을 사용했다.

 

cin의 시간초과를 막기 위해

ios_base::sync_with_stdio(0);

cin.tie(0); 

라는 코드를 써준다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 100000;
int N, M;
vector<int> A;

int binarySearch(int low, int high, int target){

    if(low > high)
        return 0;
    else
    {
        int mid = (low + high) /2 ;

        if(A[mid]==target)
            return 1;

        else if(A[mid] > target)
        {
            return binarySearch(low,mid-1,target);
        }
        else
            return binarySearch(mid+1,high,target);
    }
}



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); //cin 속도 향상 위해
    cin >> N;

    for(int i =0; i<N ;i++){
        int num;
        cin >> num;
        A.push_back(num);
    }

    sort(A.begin(),A.end());

    cin >> M;

    for (int i = 0; i < M; i++)
    {
        int num;
        cin >> num;
        cout << binarySearch(0, N - 1, num) << "\n"; //endl 쓰면 시간 초과
    }
    return 0;

}