[백준]1920. 수 찾기

[문제]

 

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

1920번: 수 찾기

 

 

[풀이]

 

배열이 주어지고 해당 배열에 찾고자 하는 숫자가 있으면 1을 출력하고 없으면 0을 출력하는 문제이다.

따라서 이진 탐색으로 풀어야겠다고 생각했다.

 

먼저 입력 받은 배열을 오름차순으로 정렬시킨다.

BinarySearch 함수에서 이진 탐색으로 해당 값을 찾으면 true를 반환하고

존재하지 않는다면 false를 반환 

 

 

[코드]

 

시간 : 72ms

 

#include <iostream>
#include <algorithm>

#define MAX 100000

using namespace std;

int N,M;
int arr[MAX]={0,};
int target;

bool BinarySearch()
{
    int mid;
    int low =0;
    int high = N-1;
    
    while(low <= high)
    {
        mid = (low + high)/2;
        if(arr[mid] == target)  return true;
        else if(arr[mid] < target)  low = mid +1;
        else    high= mid-1;
    }
    return false;
}


int main(void)
{
    
    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",&target);
    
        if(BinarySearch()) printf("1\n");
        else printf("0\n");

    }
    return 0;
    
}

 

 

지적, 조언, 질문 환영입니다.

댓글 남겨주세요~