BOJ-1920번

문제 설명

• 1920번, 수 찾기

• 난이도: 실버4

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

1 ≤ N ≤ 100,000

문제 해석

딱히 해석할 것이 없이 그냥 이진탐색문제이다.

아래 코드에서 주의할 점 중 하나는 find함수에서 vector를 레퍼런스로 받는다는 점이다.

만약 레퍼런스로 받지 않을 경우 복사하여 받게 되는데 이때 시간이 많이 걸려 시간초과를 받게 된다.

코드

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

bool find(vector<int>& v, int x) {
	int start = 0;
	int end = v.size() - 1;
	while (start < end) {
		int mid = (start + end)/2;
        if(v[mid] < x)
            start = mid + 1;
        else
            end = mid;
	}
    if(v[end] == x)
        return true;
    else
        return false;
}

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

	int N;
	cin >> N;
	vector<int> m;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		m.push_back(x);
	}
	sort(m.begin(), m.end());

	int M;
	cin >> M;
	for (int i = 0; i < M; i++) {
		int target;
		cin >> target;
		cout << find(m, target) << "\n";
	}

	return 0;
}