[백준 2776] 알고리즘 66일차 : 암기왕

www.acmicpc.net/problem/2776

2776번: 암기왕

C++ 이분탐색

두개의 정수배열이 있고 하나의 배열에서 다른 하나의 배열의 수를 찾는 간단한 문제다.

이번엔 최대값 혹은 최솟값구하는 문제도 아니고 그냥 이분탐색이다.

오히려 이런게 오랜만..

 

처음에 시간초과 걸렸었는데

ios::sync_with_stdio(false);

cin.tie(0);

쓰고 통과

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int T,N,M;
int note1[1000000];
int binarySearch(int num){
    int s = 0;
    int e = N-1;
    int mid;
    while(s <= e){
        mid = (s+e)/2;
        if(note1[mid] == num){
            return 1;
        }else if(note1[mid] < num){
            s = mid+1;
        }else{
            e = mid-1;
        }
    }
    return 0;
}
int main(){
    int note2;
    cin >> T;
    for(int t = 0 ; t < T ;t++){
        cin >> N;
        for(int i = 0 ; i < N ; i++){
            cin >> note1[i];
        }
        sort(note1, note1+N);
        cin >> M;
        for(int i = 0 ; i < M ; i++){
            cin >> note2;
            cout << binarySearch(note2) << "\n";
        }
    }
    return 0;
}