[백준] 이분 탐색 1920번: 수 찾기

문제

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을 출력한다.

Approach

사용 알고리즘: Binary Search

• 주어진 숫자들을 하나씩 확인하면서 주어진 숫자 배열에 그 숫자가 있는지 이진 탐색을 사용해 찾아보면 된다. 있을 경우 1, 없을 경우 0을 출력한다.

Source Code

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// binary search 재귀 함수 구현 
int binarySearch(vector<int> & list, int target, int left, int right)
{
    if (left > right)
        return -1;
    int mid = (left + right) / 2;
    
    if (list[mid] == target)
        return mid;
    else if (list[mid] < target)
        return binarySearch(list, target, mid + 1, right);
    else
        return binarySearch(list, target, left, mid - 1);
}


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

    int n; // 탐색할 배열의 크기 입력 받기 
    cin >> n;
    
    vector<int> nums; // 탐색할 배열의 값들 입력 받기 
    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        nums.push_back(num);
    }
    
    int m; // 배열에서 탐색해볼 숫자들 입력받기 
    cin >> m;
    
    vector<int> targets;
    for (int j = 0; j < m; j++)
    {
        int target;
        cin >> target;
        targets.push_back(target);
    }
    
    sort(nums.begin(), nums.end()); // 이분 탐색을 위해 정렬 
    
    
    for (int k = 0; k < m; k++) // 각 숫자를 확인하면서 
    {
        int result = binarySearch(nums, targets[k], 0, n - 1); // 이분 탐색을 사용해 그 숫자가 nums 벡터에 있으면 1, 없으면 0 출력 
        if (result == -1)
            cout << 0 << '\n';
        else
            cout << 1 << '\n';
    }
    
    return 0;
}