수 찾기 (feat. 백준, 1920번)

수 찾기
https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <algorithm>
using namespace std;
bool binary_search(int* p, int length, int target) {
	register int start = 0, end = length - 1, mid = (end + start) / 2;
	while ((end - start) >= 0) {
		if (p[mid] == target)
			return true;
		else if (p[mid] < target) {
			start = mid + 1;
		}
		else {
			end = mid - 1;
		}
		mid = (end + start) / 2;
	}
	return false;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, M;
	int A[100000];
	cin >> N;
	for (register int i = 0; i < N; ++i)
		cin >> A[i];
	sort(A, A + N);
	cin >> M;
	for (register int i = 0, v; i < M; ++i) {
		cin >> v;
		if (binary_search(A, A + N, v))
			cout << 1;
		else
			cout << 0;
		cout << "\n";
	}
	return 0;
}
// *&)*@*

이분탐색은 정렬이 되어 있다는 전제에서 수행될 수 있습니다.