백준 1920 - 수 찾기

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

1920번: 수 찾기

 

풀이

이분탐색을 이용하여 수를 찾는 문제이다.

탐색하려는 배열을 정렬한 후, 찾으려는 수가 배열의 중간값보다 크면 중간값 이전 값들은 고려하지 않고,

배열의 중간값보다 작다면 중간값 이후의 값들은 고려하지 않는다. 계속 범위를 줄여가다가 1) 중간값과 찾으려는 수가 일치하거나, 2) 배열의 크기가 0이 되어 끝을 가리키는 인덱스가 처음을 가리키는 인덱스보다 작아진다면 탐색을 끝낸다.

 

코드

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

int main()
{
    int n1, n2;
    cin>>n1;
    vector<long> v1;
    vector<long> v2;
    long a;

    for(int i=0; i<n1; i++)
    {
        cin>>a;
        v1.push_back(a);
    }
    cin>>n2;
    for(int i=0; i<n2; i++)
    {
        cin>>a;
        v2.push_back(a);
    }

    sort(v1.begin(),v1.end());
    for(auto i:v2)
    {
        int flag = 0;
        int right = v2.size()-1;
        int left = 0;
        while(left<=right)
        {
            int mid = (right+left)/2;
            if(i==v1[mid])
            {
                flag = 1;
                cout<<"1"<<'\n';
                break;
            }
            else if(i<v1[mid]) right = mid-1;
            else if(i>v1[mid]) left = mid+1;
        }
        if(flag==0) cout<<"0"<<'\n';
    }
    return 0;
}