[BOJ] 1920. 수 찾기

문제

www.acmicpc.net/problem/1920

1920번: 수 찾기

 

---

해설

이진탐색으로 해결하였으며 이분탐색은 정렬이 되어있어야 가능하다.

---

코드

#include<iostream>
#include<algorithm>

using namespace std;

int n[100001];
int m[100001];

int binarysearch(int low, int high, int target) {

	if (low > high) return 0;
	else {

		int mid = (low + high) / 2;
		if (n[mid] == target) return 1;
		else if (n[mid] > target)
			return binarysearch(low, mid - 1, target);
		else
			return binarysearch(mid + 1, high, target);
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int x;
	cin >> x;

	for (int i = 0; i < x; i++) cin >> n[i];

	sort(n, n + x);

	int y;
	cin >> y;

	for (int i = 0; i < y; i++) {
		cin >> m[i];
		cout << binarysearch(0, x - 1, m[i]) << '\n';
	}
	return 0;
}

 

#include <iostream>
#include <algorithm>

using namespace std;

int N, M;
int arr[500001];
int srch[500001];

int main()
{
	ios::sync_with_stdio(false);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	cin >> M;
	for (int j = 0; j < M; j++)
	{
		cin >> srch[j];
	}
	sort(arr, arr + N);
	for (int h = 0; h < M; h++)
	{
		if (binary_search(arr, arr + N, srch[h])) //binary_search 함수 사용
			cout << '1' << ' ';
		else
			cout << '0' << ' ';
	}
	cout << '\n';
	return 0;
}