문제 설명

수 찾기

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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

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

풀이 내용

이분 탐색을 하기위해선 정렬된 값들이 필요하다.
받은 값을 정렬 후 시작점과 끝점을 설정해준다.
begin = 0; end = n;
다음으로 중간점을 설정해준다.
mid = begin + end >> 1

찾을 값이 mid 값보다 작으면 end값을 mid로 바꿔주고 mid 값보다 크면 begin값을 mid로 바꿔준다.

시작값과 끝값의 차이가 2이상 날때 mid 값이 바뀌게 됨으로 begin + 1 < end 까지 수행한다.
(ex. begin = 4, end = 5이면 mid가 항상 4가 됨)

#include <iostream>
#include <algorithm>

using namespace std;

bool check(int x, int num)
{
    return x <= num;
}

int main()
{
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    int arr[100001];

    int n;
    cin >> n;

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

    sort(arr, arr + n, less<int>());

    int m;
    cin >> m;

    for (int i = 0; i < m; i++)
    {
        int num;
        cin >> num;

        int begin = 0, end = n;
        while (begin + 1 < end)
        {
            int mid = begin + end >> 1;
            if (check(arr[mid], num))
                begin = mid;
            else
                end = mid;
        }

        if (arr[begin] == num)
            cout << 1 << "\n";
        else
            cout << 0 << "\n";
    }
}