글 읽기 - 정렬 + 이분탐색 시간초과

heehcs 3년 전 0

출제자가 의도하는게 이 알고리즘이 아닌것같은데
힌트좀 주시면 감사하겠습니다.

#define loop(i,start,stop) for(int i = start; i < stop; i++)
#include <iostream>
#include <algorithm>
using  namespace std;
int a[1000005];
int T, N, M;
int x;

bool bs(int x) {
    int lo,hi;
    lo = -1;
    hi = N;

    while(lo + 1 < hi) {
        int mid = (lo+hi) / 2;
        if(a[mid] < x) {
            lo = mid;
        }
        else {
            hi = mid;
        }
    }
    return (a[hi] == x) ? true : false;
}


int main() {
    freopen("1.txt", "r", stdin);
    scanf("%d", &T);
    while(T--) {
        cin >> N;
        loop(i,0,N) {
            scanf("%d", &x);
            a[i] = x;
        }
        sort(a, a+N);

        cin >> M;
        while(M--) {
            cin >> x;
            if(bs(x)) {
                printf("1\n");
            }
            else {
                printf("0\n");
            }
        }
    }
}