[백준] 이분 탐색 - 1920. 수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

 

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

예제 입력1

5
4 1 5 2 3
5
1 3 7 9 5

 

예제 출력1

1
1
0
0
1

 

생각

처음에는 단순하게 하나씩 입력받은 수를 배열에서 있는지 체크해서 있으면 true를 리턴하는 함수를 작성해서 간단하게 풀었다. 하지만 이렇게 풀면 예제 답안은 나올지라도 시간 초과가 나서 실패하게 된다. 

이분 탐색(혹은 이진탐색)을 이용하면 시간 복잡도를 O(logN)로 줄일 수 있다. 단, 여기서 주의 할 점은 이진 탐색을 사용하는 경우 정렬이 되어 있어야한다는 것! 

 

작성한 코드

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 100000

int arr[MAX];
int n,m;
bool check = false;

void BinarySearch(int key){
    int first = 0;
    int last = n-1;
    int mid = 0;

    while(first <= last){
        mid = (first+last)/2;
        if(arr[mid] == key){
            check = true;
            return;
        }else if(arr[mid] > key){
            last = mid -1;
        }else{
            first = mid +1;
        }
    }
    check = false;
    return;
}
int main(int argc, const char * argv[]) {
    // insert code here...
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int num;
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    
    sort(arr, arr+n);
    
    cin >> m;
    for(int i=0; i<m; i++){
        cin >> num;
        BinarySearch(num);
        
        if(check){
            cout << 1 << "\n";
        }else{
            cout << 0 << "\n";
        }
    }
    return 0;
}