[백준] 1920 - 수 찾기

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

1920번: 수 찾기

 최대 10만개의 숫자목록을 받은 후, 다음에 입력받는 최대 10만개의 숫자들이 이전의 숫자 목록에 존재하는지의 여부를 확인하는 문제다. 10만개 정도의 input이 주어졌을 때, 시간복잡도가 N^2이 되어도 1000억번의 연산이 필요하다. N log N으로 시간복잡도를 끊어야 하는데, 이 문제의 경우는 검색 대상인 숫자 목록을 정렬을 시켜놓고 이분탐색을 하면 제 시간내에 문제 해결이 가능하다.

#include <iostream>
using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int N, M;
int ns[1000001];

int cmp(const void * a, const void * b)
{
    return ( *(int*)a > *(int*)b );
}

int binarySearch(int target, int startIdx, int endIdx){
    if(startIdx > endIdx){
        return 0;
    }
    int mid = (startIdx + endIdx) / 2;
    if(ns[mid] == target){
        return 1;
    }
    else if(ns[mid] > target){
        return binarySearch(target, startIdx, mid-1);
    }
    else{
        return binarySearch(target, mid+1, endIdx);
    }
}

int main(){
    scanf("%d", &N);
    for(int i=0; i<N; ++i){
        scanf("%d", &(ns[i]));
    }

    qsort(ns, N, sizeof(int), cmp);

    scanf("%d", &M);
    for(int i=0; i<M; ++i){
        int in;
        scanf("%d", &in);
        printf("%d\n", binarySearch(in, 0, N-1));
    }

    return 0;

}