(c++)백준 1920번: 수 찾기

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

1920번: 수 찾기

[풀이]

이분탐색을 사용하여 풀었다. 

※이분탐색을 하려면 배열 A를 정렬시켜야 하므로 vector자료구조를 사용하였다.

 

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

int N, M;
vector<int>A;

void Search(int n) {
	int front = 0, rear = N - 1;
	while (front <= rear) {
		int mid = (front + rear) / 2;
		
		if (A[mid] == n) {
			cout << 1 << '\n';
			return;
		}
		else if (A[mid] < n) {
			front = mid + 1;
		}
		else if (A[mid] > n) {
			rear = mid - 1;
		}
	}
	cout << 0 << '\n';
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> n;
		A.push_back(n);
	}
	//이분탐색을 하려면 정렬되어 있어야 한다!
	sort(A.begin(), A.end());
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> n;
		Search(n);
	}
	return 0;
}