백준 1920 - 수 찾기 - 이분 탐색

문제

문제링크 : https://www.acmicpc.net/problem/1920

풀이전략

1. 주어진 수중에 X라는 수가 존재하는지를 찾는 것이다. 1<=N<=100000이므로N^2으로는 해결할 수 없다. 따라서 이분 탐색을 이용해 NlogN으로 해결해야한다.
2. 어떤 수를 찾아라 == 이분 탐색으로 생각하면 된다.

코드

#include<bits/stdc++.h>

using namespace std;


vector<int> num;
vector<int> numFind;
int N, M;

int BinarySearch(int lt, int rt, int n){
    int mid = (lt+rt) / 2;
    
    if(lt > rt){
        return 0;
    }
    else{
        if(n == num[mid]){
            return 1;
        }
        else if(n > num[mid]){
            return BinarySearch(mid+1, rt, n);
        }
        else if(n < num[mid]){
            return BinarySearch(lt, mid-1, n);
        }
    }
    
    return 0;
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N;
    int tmp;
    for(int i=0; i<N; i++){
        cin >> tmp;
        num.push_back(tmp);
    }
    sort(num.begin(), num.end());
    cin >> M;
    for(int i=0; i<M; i++){
        cin >> tmp;
        numFind.push_back(tmp);
    }

    for(int i=0; i<M; i++){
        cout<<BinarySearch(0, num.size(), numFind[i])<<"\n";
    }
    return 0;
}

소감

나는 이상하게 항상 재귀가 편해서 재귀로 짰는데, 다른 분들은 while(lt <= rt) 로 조건을 주고 lt, rt를 mid-1, mid+1로 각각 조건을 주어 바꾸셨다. 이 또한 나도 할줄 알아야한다.