[C++] 백준 1920 - 수 찾기

백준 1920 : 수 찾기
난이도 : 실버 4

시간 : 20분 소요

 

 

 

문제

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

1920번: 수 찾기

풀이 과정

 

이진 탐색을 활용한 간단한 문제이다.

 

 

최종 코드

#include <iostream>
#include <cstring>
#include <algorithm>

#define MAX 100001

using namespace::std;

int N, M;

int arr[MAX];
int fin[MAX];

bool check(int f, int b, int n){
    int mid = arr[(f+b)/2];
    if(mid == n){
        return true;
    }
    if(n<arr[f] || n>arr[b]){
        return false;
    }
    
    bool tmp = false;
    
    if(mid<n){
        tmp = check((f+b)/2+1, b, n);
    }else if(mid>n){
        tmp = check(0,(f+b)/2-1, n);
    }
    return tmp;
}

int main(){
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        scanf("%d", &arr[i]);
    }
    sort(arr, arr+N);
    
    scanf("%d", &M);
    for(int i=0; i<M; i++){
        scanf("%d", &fin[i]);
        if(check(0, N-1, fin[i])){
            fin[i] = 1;
        }else{
            fin[i] = 0;
        }
    }
    
    for(int i=0; i<M; i++){
        printf("%d\n", fin[i]);
    }
}