백준 1920번 수 찾기

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

입력

첫째 줄: 자연수 N (1 <= N <= 100,000)
둘째 줄: N개의 정수(배열 A의 요소들)
셋째 줄: 자연수 M ( 1 <= M <= 100,000)
넷째 줄: M개의 정수, 이 수들이 배열 A 안에 존재하는지 확인

출력

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

입출력 예제

해결 방법

이분탐색을 이용한다. 기본적인 해결 과정은 아래와 같다.

1. 배열을 정렬한다.
2. 탐색 범위 내에서 배열의 중간 인덱스를 구한다.
3. 중간 인덱스의 값을 val 값과 비교한다.
4. 값이 중간 인덱스의 값과 같으면 true를 반환하고, 값이 중간 값보다 크면 오른쪽 부분을 탐색하고, 작으면 왼쪽 부분을 탐색한다.
   

소스 코드

#include <iostream>
#include <algorithm>
#define MAX_SIZE 100001

using namespace std;

int arr1[MAX_SIZE];
int arr2[MAX_SIZE];

bool binarySearch(int val, int idx) //val: arr2[i], idx: n
{
        int left = 0;
        int right = idx-1;
        int mid;

        while(left<=right){
                mid = (left + right) / 2;

                if(arr1[mid] == val)
                        return true;
                else if(arr1[mid] < val)
                        left = mid+1;
                else
                        right = mid-1;
        }

        return false;
}

int main()
{
        int n, m;

        cin>>n;

        for(int i=0;i<n;i++){
                cin>>arr1[i];
        }

        cin>>m;

        for(int i=0;i<m;i++){
                cin>>arr2[i];
        }

        sort(arr1, arr1+n);

        for(int i=0;i<m;i++){
                if(binarySearch(arr2[i], n)){
                        cout<<1<<'\n';
                }
                else
                        cout<<0<<'\n';
        }

        return 0;
}