✅ 이진탐색

문제

링크

1. 문제 접근 및 해결 로직

상근이의 카드와 주어진 카드들을 하나씩 비교하면서 판별하려면
MxN 번이 걸린다. 최대 500,000x500,000 이므로 선형완전탐색으로는 풀 수 없다.

따라서 이진탐색을 수행한다.

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int N, M;
int arr[500001], target[500001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    sort(arr, arr + N);

    cin >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> target[i];
    }
    
    int left, mid, right;
    bool flag;
    for(int i=0;i<M;i++)
    {
        left = 0;
        right = N-1;
        mid = (left+right)/2;
        flag = false;
        
        while(left<=right)
        {
            if(arr[mid] == target[i])
            {
                flag = true;
                break;
            }
            if (arr[mid] < target[i])
            {
                left = mid + 1;
                mid = (left + right)/2;
            }
            if (arr[mid] > target[i])
            {
                right = mid - 1;
                mid = (left + right) / 2;
            }
        }
        
        if(flag==true)cout << 1 << " ";
        else cout << 0 << " ";
    }

    return 0;
}

3. 시간 복잡도 분석

$O(M*log_2N)$

4. 문제에서 중요한 부분

이진탐색을 떠올리는게 중요